On recognizing words that are squares for the shuffle product

DOI10.1007/978-3-642-38536-0_21MaRDI QIDQ4928489zbMATH OpenOpenAlexFDO

Authors Romeo Rizzi, Stéphane Vialette

Publication date 14 June 2013

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://hal-upec-upem.archives-ouvertes.fr/hal-00725429/file/article.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Recognizing binary shuffle squares is \textsf{NP}-hard
• A note on square-free shuffles of words
• Square-free shuffles of words
• Unshuffling permutations
• Algorithmic and algebraic aspects of unshuffling permutations

Cited in

(14)

• On recognising words that are squares for the shuffle product
• Algorithmic and algebraic aspects of unshuffling permutations
• String shuffle: circuits and graphs
• Unshuffling permutations
• Square-free words with square-free self-shuffles
• Square-free shuffles of words
• Infinite self-shuffling words
• A note on square-free shuffles of words
• Decision problems on copying and shuffling
• Recognizing binary shuffle squares is \textsf{NP}-hard
• Subsequence covers of words
• Unshuffling a square is NP-hard
• The Shuffle Product: New Research Directions
• On comparing deterministic finite automata and the shuffle of words

This page was built for publication: On recognizing words that are squares for the shuffle product

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928489)