Abstract
We investigate the equational theory of several fragments of CCS modulo (strong) bisimilarity with special attention to restriction and relabelling. The largest fragment we consider includes action prefixing, choice, parallel composition without communication, restriction and relabelling. We present a finite equational base (i.e., a finite ground-complete and omega-complete axiomatisation) for it, including the left merge from ACP as auxiliary operation to facilitate the axiomatisation of parallel composition.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aceto, L., Fokkink, W., Ingólfsdóttir, A., Luttik, B.: A finite equational base for CCS with left merge and communication merge. ACM Trans. Comput. Log. (2008). To appear (available as http://tocl.acm.org/accepted/310luttik.pdf).
Baeten, J.C.M., Bergstra, J.A.: Global renaming operators in concrete process algebra. Information and Computation 78(3), 205–245 (1988)
Bergstra, J., Klop, J.: Process algebra for synchronous communication. Information and Control 60(1-3), 109–137 (1984)
Birkhoff, G.: On the structure of abstract algebras. Proceedings of the Cambridge Philosophical Society 31, 433–454 (1935)
Christensen, S., Hirshfeld, Y., Moller, F.: Decidable subsets of CCS. The Computer Journal 37(4), 233–242 (1994)
Hennessy, M., Milner, R.: Algebraic laws for nondeterminism and concurrency. Journal of the ACM (JACM) 32(1), 137–161 (1985)
Milner, R.: Flowgraphs and flow algebras. Journal of the ACM (JACM) 26(4), 794–818 (1979)
Milner, R.: A Calculus of Communicating Systems. Springer (1980)
Milner, R.: Communication and Concurrency. Prentice-Hall (1989)
Milner, R., Moller, F.: Unique decomposition of processes. Theoret. Comput. Sci. 107, 357–363 (1993)
Moller, F.: Axioms for Concurrency. Ph.D. thesis (1989)
Park, D.: Concurrency and automata on infinite sequences. In: P. Deussen (ed.) 5$th$ GI Conference, it Lecture Notes in Computer Science, vol. 104, pp. 167–183. Springer (1981)
de Simone, R.: Higher level synchronization devices in SCCS-Meije. Theoretical Computer Science 37, 245–267 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 IFIP International Federation for Information Processing
About this paper
Cite this paper
Aceto, L., Ingólfsdóttir, A., Luttik, B., van Tilburg, P. (2008). Finite Equational Bases for Fragments of CCS with Restriction and Relabelling. In: Ausiello, G., Karhumäki, J., Mauri, G., Ong, L. (eds) Fifth Ifip International Conference On Theoretical Computer Science – Tcs 2008. IFIP International Federation for Information Processing, vol 273. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-09680-3_22
Download citation
DOI: https://doi.org/10.1007/978-0-387-09680-3_22
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-09679-7
Online ISBN: 978-0-387-09680-3
eBook Packages: Computer ScienceComputer Science (R0)