On Recognizing Words That Are Squares for the Shuffle Product
From MaRDI portal
Publication:4928489
DOI10.1007/978-3-642-38536-0_21zbMath1381.68134OpenAlexW178616653MaRDI QIDQ4928489
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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (11)
Unshuffling a square is NP-hard ⋮ Square-free words with square-free self-shuffles ⋮ Subsequence covers of words ⋮ On the complexity and decidability of some problems involving shuffle ⋮ On recognising words that are squares for the shuffle product ⋮ Infinite self-shuffling words ⋮ Square-free shuffles of words ⋮ Algorithmic and algebraic aspects of unshuffling permutations ⋮ String shuffle: circuits and graphs ⋮ Recognizing binary shuffle squares is \textsf{NP}-hard ⋮ The Shuffle Product: New Research Directions
This page was built for publication: On Recognizing Words That Are Squares for the Shuffle Product
