[en] 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 up to bisimilarity. Then, we prove that replacing the operation for pure interleaving by ACP-style parallel composition gives a further increase in expressiveness. 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.
Disciplines :
Computer science
Identifiers :
UNILU:UL-CONFERENCE-2011-040
Author, co-author :
Baeten, J.
Luttik, B.
Muller, Tim ; University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
van Tilburg, P.
External co-authors :
no
Language :
English
Title :
Expressiveness modulo Bisimilarity of Regular Expressions with Parallel Composition
Publication date :
2010
Event name :
Proc. 17th International Workshop on Expressiveness in Concurrency
Event date :
2010
Main work title :
Proc. 17th International Workshop on Expressiveness in Concurrency
Collection name :
Electronic Proceedings in Theoretical Computer Science
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.
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.
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.
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.
Bergstra, J. A., Bethke, I. and Ponse, A. (1994) Process algebra with iteration and nesting. The Computer Journal 37 (4) 243-258.
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.
Bergstra, J. A. and Klop, J. W. (1984) Process algebra for synchronous communication. Information and Control 60 (1-3) 109-137.
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.
Glabbeek, R. J. V. and Weijland, W. P. (1996) Branching time and abstraction in bisimulation semantics. Journal of the ACM 43 (3) 555-600.
Gorla, D. (2010) Towards a unified approach to encodability and separation results for process calculi. Information and Computation 208 (9) 1031-1053.
Hopcroft, J. E., Motwani, R. and Ullman, J. D. (2006) Introduction to Automata Theory, Languages, and Computation, Pearson.
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.
Milner, R. (1984) A complete inference system for a class of regular behaviours. Journal of Computer System Science 28 (3), 439-466.
Milner, R. (1989) Communication and Concurrency, Prentice-Hall International, Englewood Cliffs.
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.
Plotkin, G. D. (2004) A structural approach to operational semantics. Journal of Logic and Algebraic Programming 60-61 17-139.
Vrancken, J. L. M. (1997) The algebra of communicating processes with empty process. Theoretical Computer Science 177 (2) 287-328.
