Shuffle and scattered deletion closure of languages

DOI10.1016/S0304-3975(99)00277-7zbMath0946.68074MaRDI QIDQ1575737

Lila Kari, Masami Ito, Gabriel Thierrin

Publication date: 21 August 2000

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

zbMATH Keywords

shuffle closure; shuffle operation; insertion and deletion operations; maximal shuffle residual; RSS-type laguage; shuffle residual

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

OPERATIONS ON TRAJECTORIES WITH APPLICATIONS TO CODING AND BIOINFORMATICS, Deletion along trajectories, Well quasi-orders generated by a word-shuffle rewriting, Aspects of shuffle and deletion on trajectories, Representing recursively enumerable languages by iterated deletion, SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES, Well quasi-orders, unavoidable sets, and derivation systems, Well Quasi-orders in Formal Language Theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Infinite hierarchy of shuffle expressions over a finite alphabet
• Extending regular expressions with iterated shuffle
• Nesting of shuffle closure is important
• Literal shuffle
• Nonfinite axiomatizability of the equational theory of shuffle
• Flow languages equal recursively enumerable languages
• The universe problem for unrestricted flow languages
• Monogenic \(e\)-closed languages and dipolar words
• Insertion and deletion closure of languages
• Dense property of initial literal shuffles
• Nonfinite axiomatizability of shuffle inequalities