The Shuffle Product: New Research Directions

DOI10.1007/978-3-319-15579-1_5zbMath1451.68161OpenAlexW200373251MaRDI QIDQ2799163

Antonio Restivo

Publication date: 8 April 2016

Published in: Language and Automata Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-15579-1_5

zbMATH Keywords

shufflestar-free languagesintermixed languagesshuffle squares

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45)

Related Items (10)

Automata-theoretical regularity characterizations for the iterated shuffle on commutative regular languages ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Shuffle product of regular languages: results and open problems ⋮ Unnamed Item ⋮ Sequences of words defined by two-way transducers ⋮ Recognizing binary shuffle squares is \textsf{NP}-hard ⋮ Unnamed Item ⋮ State complexity investigations on commutative languages -- the upward and downward closure, commutative aperiodic and commutative group languages ⋮ Regularity conditions for iterated shuffle on commutative regular languages ⋮ Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Regular languages and partial commutations
• Square-free words with square-free self-shuffles
• Square-free shuffles of words
• The expressive power of the shuffle product
• The equation \(a_ M=b^ Nc^ P\) in a free group
• On the complexity of iterated shuffle
• Efficient recognition of rational relations
• An algorithm for a merge recognition problem
• On the computational complexity of a merge recognition problem
• Star-free trace languages
• Variétés de langages et opérations
• Reconstructing a history of recombinations from a set of sequences
• Shuffle on positive varieties of languages
• Synchronized shuffles
• Unshuffling a square is NP-hard
• A Note on Square-Free Shuffles of Words
• Theme and Variations on the Concatenation Product
• A Robust Class of Regular Languages
• Process Algebra
• Software Descriptions with Flow Expressions
• On Recognizing Words That Are Squares for the Shuffle Product
• Mappings of languages by two-tape devices

This page was built for publication: The Shuffle Product: New Research Directions