SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES

DOI10.1142/S0129054102001461zbMath1067.68085MaRDI QIDQ3021987

Sándor Vágvölgyi, Kai Salomaa, Cezar Campeanu

Publication date: 22 June 2005

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Deletion along trajectories ⋮ Tree shuffle ⋮ RESTRICTED SETS OF TRAJECTORIES AND DECIDABILITY OF SHUFFLE DECOMPOSITIONS ⋮ On Language Decompositions and Primality ⋮ Algorithmic decomposition of shuffle on words ⋮ Language Decompositions, Primality, and Trajectory-Based Operations ⋮ On Shuffling a Word with its Letter-to-Letter Substitution ⋮ Language equations ⋮ Decidability of trajectory-based equations

Cites Work

• Extending regular expressions with iterated shuffle
• Shuffle on trajectories: Syntactic constraints
• Families of locally testable languages
• Shuffle and scattered deletion closure of languages
• Optimal estimation on the order of local testability of finite automata
• Shuffle languages are in P
• Shuffle factorization is unique
• Thin and slender languages
• Computing the Order of a Locally Testable Automaton