On the enlargement of the class of regular languages by the shuffle closure (Q760799)

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.