Shuffle and scattered deletion closure of languages

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

Masami Ito, Gabriel Thierrin, Lila Kari

Publication date: 21 August 2000

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00277-7

zbMATH Keywords

shuffle closureshuffle operationinsertion and deletion operationsmaximal shuffle residualRSS-type laguageshuffle residual

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (15)

Minimal forbidden subwords ⋮ Deletion along trajectories ⋮ \(\mathcal{L}\)-reduction computation revisited ⋮ Well quasi-orders generated by a word-shuffle rewriting ⋮ Tree shuffle ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Well Quasi-orders in Formal Language Theory ⋮ On Language Decompositions and Primality ⋮ SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES ⋮ On the computing powers of \(\mathcal{L}\)-reductions of insertion languages ⋮ Aspects of shuffle and deletion on trajectories ⋮ OPERATIONS ON TRAJECTORIES WITH APPLICATIONS TO CODING AND BIOINFORMATICS ⋮ On bonded sequential and parallel insertion systems ⋮ Representing recursively enumerable languages by iterated deletion ⋮ Well quasi-orders, unavoidable sets, and derivation systems

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

This page was built for publication: Shuffle and scattered deletion closure of languages