On the enlargement of the class of regular languages by the shuffle closure. (English) Zbl 0555.68043

The author examines the effect of adding two new operations to regular expressions: the shuffle and shuffle closure operators. These give flow expressions and pseudo-flow languages. (Flow languages are obtained when some of the symbols are interpreted as lock and signal instructions.) The original motivation for the study of flow expressions was the description of allowable interleavings of computations in a concurrent environment.
The author shows that pseudo-flow languages are properly contained in the context-sensitive languages. [Flow languages are exactly the recursively enumerable languages.] The language \(\{a^ nb^ nc^ n:\) \(n\geq 1\}\) is shown to be a non-pseudo-flow language via a pumping lemma, which the author establishes.
Reviewer: D.Wood


68Q45 Formal languages and automata
Full Text: DOI


[1] Aho, A.; Ullman, J., The theory of parsing, translation and compiling, (1972), Prentice-Hall Englewood Cliffs, NJ
[2] Araki, T.; Tokura, N., Flow languages equal recursively enumerable languages, Acta inform., 15, 209-217, (1981) · Zbl 0456.68093
[3] Ginzburg, A.; Yoeli, M., Vector addition systems and regular languages, J. comput. syst. sci., 20, 277-284, (1980) · Zbl 0446.68043
[4] Karp, R.M.; Miller, R.E., Parallel program schemata, J. comput. syst. sci., 3, 147-195, (1969) · Zbl 0198.32603
[5] Leonarski, D., Shuffle of formal languages, its properties and applications to some problems in the theory of concurrency, (1982), Institute of Informatics, University of Warsaw, Unpublished manuscript
[6] Shaw, A.C., Software descriptions with flow expressions, IEEE trans. software engrg., SE-4, 3, 242-254, (1978) · Zbl 0381.68035
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.