Descriptive powers of synchronized shuffle grammars and synchronized production systems
Toshiro Araki, Hirotaka Uoi, Shoji Kosai, Nobuki Tokura · Systems and Computers in Japan · 1985
Abstract As models to describe the concurrent systems with synchronized mechanism, synchronized shuffle grammar and synchronized production system (SPS) have been proposed. The synchronized shuffle grammar is defined by the triplet composed of a shuffle grammar G, synchronizing language LC and a homeomorphism h. The language generated by is defined as L(G) = h (L(G) LC). As a subclass of the synchronized shuffle grammar, this paper considers a class syncRSG (sync ERSG), where G is an (extended) regular shuffle grammar and Lc is an arbitrary regular language. SPS can also be defined as a pair of extended context‐free grammar and a state‐transition machine. This paper considers as its subclass, the context‐free SPS which is a pair of a context‐free grammar and a finite automaton. It is shown that there exist some subclass.es in syncRSG (sync ERSG) and context‐free SPS, which generate the same class of formal languages. It is also shown that there exists a certain hierarchical relation, and the full descriptive powers of syncRSG (syncERSG) and context‐free SPS are the equivalent to that of Petri net.