Reference : Expressiveness modulo Bisimilarity of Regular Expressions with Parallel Composition
Scientific congresses, symposiums and conference proceedings : Paper published in a book
Engineering, computing & technology : Computer science
http://hdl.handle.net/10993/25970
Expressiveness modulo Bisimilarity of Regular Expressions with Parallel Composition
English
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. [> >]
2010
Proc. 17th International Workshop on Expressiveness in Concurrency
Electronic Proceedings in Theoretical Computer Science
Yes
Proc. 17th International Workshop on Expressiveness in Concurrency
2010
[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.
http://hdl.handle.net/10993/25970
10.1017/S0960129514000309

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Limited access
1011.6429v1.pdfPublisher postprint143.29 kBRequest a copy

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.