Hostname: page-component-74656f9884-g96k6 Total loading time: 0 Render date: 2026-11-10T12:13:02.462Z Has data issue: false hasContentIssue false
  • English
  • Français

Expressiveness modulo bisimilarity of regular expressions with parallel composition

Published online by Cambridge University Press:  02 January 2015

JOS C. M. BAETEN ,
BAS LUTTIK ,
TIM MULLER  and
PAUL VAN TILBURG
JOS C. M. BAETEN
Affiliation:
CWI, P.O. Box 94079, NL-1090 GB, the Netherlands Email: Jos.Baeten@cwi.nl Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, the Netherlands Email: s.p.luttik@tue.nl, paul@luon.net
BAS LUTTIK
Affiliation:
Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, the Netherlands Email: s.p.luttik@tue.nl, paul@luon.net Department of Computer Science, Vrije Universiteit Amsterdam, De Boelelaan 1081, NL-1081 HV Amsterdam, the Netherlands
TIM MULLER
Affiliation:
Faculty of Science, Technology and Communication, University of Luxembourg, 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg Email: tim.muller@uni.lu
PAUL VAN TILBURG
Affiliation:
Department of Mathematics and Computer Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, the Netherlands Email: s.p.luttik@tue.nl, paul@luon.net
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The languages accepted by finite automata are precisely the languages denoted by regular expressions. In contrast, finite automata may exhibit behaviours that cannot be described by regular expressions up to bisimilarity. In this paper, we consider extensions of the theory of regular expressions with various forms of parallel composition and study the effect on expressiveness. First we prove that adding pure interleaving to the theory of regular expressions strictly increases its expressiveness modulo bisimilarity. Then, we prove that replacing the operation for pure interleaving by ACP-style parallel composition gives a further increase in expressiveness, still insufficient, however, to facilitate the expression of all finite automata up to bisimilarity. Finally, we prove that the theory of regular expressions with ACP-style parallel composition and encapsulation is expressive enough to express all finite automata up to bisimilarity. Our results extend the expressiveness results obtained by Bergstra, Bethke and Ponse for process algebras with (the binary variant of) Kleene's star operation.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 26 , Special Issue 6: Special Issue: Express'10 , September 2016 , pp. 933 - 968
Copyright
Copyright © Cambridge University Press 2015 

References

Baeten, J. C. M., Basten, T. and Reniers, M. A. (2010) Process Algebra: Equational Theories of Communicating Processes, Cambridge Tracts in Theoretical Computer Science volume 50, Cambridge University Press.Google Scholar
Baeten, J. C. M., Corradini, F. and Grabmayer, C. A. (2007) A characterization of regular expressions under bisimulation. Journal of the ACM 54 (2) 6.1–28.Google Scholar
Baeten, J. C. M. and van Glabbeek, R. J. (1987) Merge and termination in process algebra. In: Nori, K. V. (ed.) Foundations of Software Technology and Theoretical Computer Science. Springer Lecture Notes in Computer Science 287 153–172.Google Scholar
Baeten, J. C. M. and Verhoef, C. (1993) A congruence theorem for structured operational semantics with predicates. In: Best, E. (ed.) Conference on Concurrency Theory. Springer Lecture Notes in Computer Science 715 477–492.CrossRefGoogle Scholar
Bergstra, J. A., Bethke, I. and Ponse, A. (1994) Process algebra with iteration and nesting. The Computer Journal 37 (4) 243–258.Google Scholar
Bergstra, J. A., Fokkink, W. and Ponse, A. (2001) Process algebra with recursive operations. In: Bergstra, J. A., Ponse, A. J. and Smolka, S. A. (eds.) Handbook of Process Algebra, Elsevier 333–389.Google Scholar
Bergstra, J. A. and Klop, J. W. (1984) Process algebra for synchronous communication. Information and Control 60 (1–3) 109–137.Google Scholar
Fröschle, S. B. and Valencia, F. D. (eds.) (2010) Proceedings 17th International Workshop on Expressiveness in Concurrency. Electronic Proceedings in Theoretical Computer Science 41 1–15.Google Scholar
Glabbeek, R. J. V. and Weijland, W. P. (1996) Branching time and abstraction in bisimulation semantics. Journal of the ACM 43 (3) 555–600.Google Scholar
Gorla, D. (2010) Towards a unified approach to encodability and separation results for process calculi. Information and Computation 208 (9) 1031–1053.Google Scholar
Hopcroft, J. E., Motwani, R. and Ullman, J. D. (2006) Introduction to Automata Theory, Languages, and Computation, Pearson.Google Scholar
Koymans, C. J. P. and Vrancken, J. L. M. (1985) Extending process algebra with the empty process ϵ, Logic Group Preprint Series 1, State University of Utrecht.Google Scholar
Milner, R. (1984) A complete inference system for a class of regular behaviours. Journal of Computer System Science 28 (3), 439–466.Google Scholar
Milner, R. (1989) Communication and Concurrency, Prentice-Hall International, Englewood Cliffs.Google Scholar
Park, D. (1981) Concurrency and automata on infinite sequences. In: Deussen, P. (ed.) Proceedings of the 5th GI Conference. Springer-Verlag Lecture Notes in Computer Science 104, Karlsruhe, Germany 167–183.Google Scholar
Plotkin, G. D. (2004) A structural approach to operational semantics. Journal of Logic and Algebraic Programming 60–61 17–139.Google Scholar
Vrancken, J. L. M. (1997) The algebra of communicating processes with empty process. Theoretical Computer Science 177 (2) 287–328.CrossRefGoogle Scholar