On recognizing words that are squares for the shuffle product

DOI10.1007/978-3-642-38536-0_21zbMATH Open1381.68134OpenAlexW178616653MaRDI QIDQ4928489FDOQ4928489

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

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

Mathematics Subject Classification ID

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

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
• A note on square-free shuffles of words
• Infinite self-shuffling 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)