Infinite hierarchy of shuffle expressions over a finite alphabet

DOI10.1016/0020-0190(90)90179-2zbMath0706.68063OpenAlexW2102326929MaRDI QIDQ918713

Joanna Jȩdrzejowicz

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90179-2

zbMATH Keywords

shuffle closure hierarchyshuffle operator

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Shuffle and scattered deletion closure of languages ⋮ Characterization and complexity results on jumping finite automata

Cites Work

• 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
• Nesting of shuffle closure is important
• Infinite hierarchy of expressions containing shuffle closure operator
• The power of synchronizing operations on strings
• Transition graphs and the star-height of regular events
• Shuffle languages, Petri nets, and context-sensitive grammars
• Homomorphisms that preserve star height

This page was built for publication: Infinite hierarchy of shuffle expressions over a finite alphabet