Extending regular expressions with iterated shuffle

DOI10.1016/0304-3975(85)90221-XzbMath0574.68069MaRDI QIDQ1063422

Matthias Jantzen

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Petri net languagesmulticounter languagequasi- realtimeshuffle expressions

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 (24)

The regular-language semantics of second-order idealized ALGOL ⋮ Nesting of shuffle closure is important ⋮ The Frobenius problem for the shuffle operation ⋮ Unshuffling a square is NP-hard ⋮ Infinite hierarchy of expressions containing shuffle closure operator ⋮ The equational theory of pomsets ⋮ Well quasi-orders generated by a word-shuffle rewriting ⋮ Tree shuffle ⋮ Jumping Finite Automata: Characterizations and Complexity ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ On (left) partial shuffle ⋮ Infinite hierarchy of shuffle expressions over a finite alphabet ⋮ Well Quasi-orders in Formal Language Theory ⋮ A P-complete language describable with iterated shuffle ⋮ SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES ⋮ String shuffle: circuits and graphs ⋮ Lower Space Bounds for Accepting Shuffle Languages ⋮ Shuffle and scattered deletion closure of languages ⋮ Well quasi-orders, unavoidable sets, and derivation systems ⋮ Shuffle languages are in P ⋮ On the complexity of iterated shuffle ⋮ Extending regular expressions with iterated shuffle ⋮ The commutative closure of shuffle languages over group languages is regular ⋮ Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the enlargement of the class of regular languages by the shuffle closure
• On the complexity of iterated shuffle
• Extending regular expressions with iterated shuffle
• Parallel system schemas and their relation to automata
• Flow languages equal recursively enumerable languages
• Relations of flow languages to Petri net languages
• The power of synchronizing operations on strings
• Remarks on blind and partially blind one-way multicounter machines
• Rational sets in commutative monoids
• Very special languages and representations of recursively enumerable languages via computation histories
• Shuffle languages, Petri nets, and context-sensitive grammars
• Software Descriptions with Flow Expressions
• An approach to software system modelling and analysis

This page was built for publication: Extending regular expressions with iterated shuffle