We consider forkable regular expressions, which enrich regular expressions with a fork operator, to establish a formal basis for static and dynamic analysis of the communication behavior of concurrent programs. We define a novel compositional semantics for forkable expressions, establish their fundamental properties, and define derivatives for them as a basis for the generation of automata, for matching, and for language containment tests. Forkable expressions may give rise to non-regular languages, in general, but we identify sufficient conditions on expressions that guarantee finiteness of the automata construction via derivatives.
The latter connection is made precise by Garg and Ragunath @cite_6 , who study concurrent regular expressions (CRE), which are shuffle expressions extended with synchronous composition. They show that the class of CRE languages is equal to the class of Petri net languages. The proof requires the presence of synchronous composition. Forkable expressions do not support synchronous composition, but they are equivalent to , which are also defined by Garg and Ragunath and shown to be strictly less powerful than CREs.
@cite_6
2067131306
Abstract We define algebraic systems called concurrent regular expressions which provide a modular description of languages of Petri nets. Concurrent regular expressions are extension of regular expressions with four operators - interleaving, interleaving closure, synchronous composition and renaming. This alternative characterization of Petri net languages gives us a flexible way of specifying concurrent systems. Concurrent regular expressions are modular and, hence, easier to use for specification. The proof of equivalence also provides a natural decomposition method for Petri nets.