Shuffle languages, Petri nets, and context-sensitive grammars

DOI10.1145/358746.358767zbMath0471.68063OpenAlexW1965308680MaRDI QIDQ3926067

Jay L. Gischer

Publication date: 1981

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/358746.358767

zbMATH Keywords

regular languagesvector machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items (17)

Infinite unfair shuffles and associativity ⋮ Nesting of shuffle closure is important ⋮ Unshuffling a square is NP-hard ⋮ Infinite hierarchy of expressions containing shuffle closure operator ⋮ The equational theory of pomsets ⋮ An application of temporal projection to interleaving concurrency ⋮ Axiomatizing shuffle and concatenation in languages ⋮ Shuffled languages -- representation and recognition ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Infinite hierarchy of shuffle expressions over a finite alphabet ⋮ A Note on Multidimensional Dyck Languages ⋮ String shuffle: circuits and graphs ⋮ Lower Space Bounds for Accepting Shuffle Languages ⋮ Algorithmic Analysis of Array-Accessing Programs ⋮ Synchronized shuffles ⋮ On the complexity of iterated shuffle ⋮ Extending regular expressions with iterated shuffle

This page was built for publication: Shuffle languages, Petri nets, and context-sensitive grammars