Regularity of BPA-systems is decidable

S. Mauw; H. Mulder

doi:10.1007/BFb0014996

Regularity of BPA-systems is decidable

S. Mauw, H. Mulder

Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

It is decidable whether a system in Basic Process Algebra (BPA) is regular with respect to bisimulation semantics. Basic operators in BPA are alternative composition, sequential composition and guarded recursion. A system is regular if the interpretations of all process variables defined in the system have finitely many states. We present an effective method to transform a BPA specification into a linear specification whenever possible.

Original language	English
Title of host publication	CONCUR'94 (Proceedings 5th International Conference on Concurrency Theory, Uppsala, Sweden, August 22-25, 1994)
Editors	B. Jonsson, J. Parrow
Publisher	Springer
Pages	34-47
ISBN (Print)	3-540-58329-7
DOIs	https://doi.org/10.1007/BFb0014996
Publication status	Published - 1994

Publication series

Name	Lecture Notes in Computer Science
Volume	836
ISSN (Print)	0302-9743

Access to Document

10.1007/BFb0014996

Cite this

@inproceedings{32e0d2ca3e3f4053b68e5add0f3aeec8,

title = "Regularity of BPA-systems is decidable",

abstract = "It is decidable whether a system in Basic Process Algebra (BPA) is regular with respect to bisimulation semantics. Basic operators in BPA are alternative composition, sequential composition and guarded recursion. A system is regular if the interpretations of all process variables defined in the system have finitely many states. We present an effective method to transform a BPA specification into a linear specification whenever possible.",

author = "S. Mauw and H. Mulder",

year = "1994",

doi = "10.1007/BFb0014996",

language = "English",

isbn = "3-540-58329-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "34--47",

editor = "B. Jonsson and J. Parrow",

booktitle = "CONCUR'94 (Proceedings 5th International Conference on Concurrency Theory, Uppsala, Sweden, August 22-25, 1994)",

address = "Germany",

}

Regularity of BPA-systems is decidable. / Mauw, S.; Mulder, H.
CONCUR'94 (Proceedings 5th International Conference on Concurrency Theory, Uppsala, Sweden, August 22-25, 1994). ed. / B. Jonsson; J. Parrow. Springer, 1994. p. 34-47 (Lecture Notes in Computer Science; Vol. 836).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Regularity of BPA-systems is decidable

AU - Mauw, S.

AU - Mulder, H.

PY - 1994

Y1 - 1994

N2 - It is decidable whether a system in Basic Process Algebra (BPA) is regular with respect to bisimulation semantics. Basic operators in BPA are alternative composition, sequential composition and guarded recursion. A system is regular if the interpretations of all process variables defined in the system have finitely many states. We present an effective method to transform a BPA specification into a linear specification whenever possible.

AB - It is decidable whether a system in Basic Process Algebra (BPA) is regular with respect to bisimulation semantics. Basic operators in BPA are alternative composition, sequential composition and guarded recursion. A system is regular if the interpretations of all process variables defined in the system have finitely many states. We present an effective method to transform a BPA specification into a linear specification whenever possible.

U2 - 10.1007/BFb0014996

DO - 10.1007/BFb0014996

M3 - Conference contribution

SN - 3-540-58329-7

T3 - Lecture Notes in Computer Science

SP - 34

EP - 47

BT - CONCUR'94 (Proceedings 5th International Conference on Concurrency Theory, Uppsala, Sweden, August 22-25, 1994)

A2 - Jonsson, B.

A2 - Parrow, J.

PB - Springer

ER -

Regularity of BPA-systems is decidable

Abstract

Publication series

Access to Document

Fingerprint

Cite this