On the enlargement of the class of regular languages by the shuffle closure

DOI10.1016/0020-0190(83)90023-6zbMath0555.68043OpenAlexW2102729777MaRDI QIDQ760799

Joanna Jȩdrzejowicz

Publication date: 1983

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(83)90023-6

zbMATH Keywords

shuffleregular expressionsrecursively enumerable languagescontext-sensitive languagesflow expressionspseudo- flow languagesshuffle closure

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (9)

Nesting of shuffle closure is important ⋮ Infinite hierarchy of expressions containing shuffle closure operator ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Infinite hierarchy of shuffle expressions over a finite alphabet ⋮ A P-complete language describable with iterated shuffle ⋮ Lower Space Bounds for Accepting Shuffle Languages ⋮ Shuffle languages are in P ⋮ Insertion languages ⋮ Extending regular expressions with iterated shuffle

Cites Work

• Vector addition systems and regular languages
• Flow languages equal recursively enumerable languages
• Parallel program schemata
• Optimization of LR(k) parsers
• Software Descriptions with Flow Expressions

This page was built for publication: On the enlargement of the class of regular languages by the shuffle closure