Recognizing binary shuffle squares is \textsf{NP}-hard

DOI10.1016/J.TCS.2019.01.012MaRDI QIDQ2285126zbMATH OpenOpenAlexFDO

Authors Laurent Bulteau, Stéphane Vialette

Publication date 16 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.01.012

zbMATH Keywords

binary alphabetsNP-hardnessshuffle productstrings

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics on words (68R15)

Recommendations

• On recognizing words that are squares for the shuffle product
• Unshuffling a square is NP-hard
• On the complexity of iterated shuffle
• A note on square-free shuffles of words
• Algorithmic and algebraic aspects of unshuffling permutations

Cites work

• A note on square-free shuffles of words
• A short proof that shuffle squares are 7-avoidable
• Acyclic coloring of graphs and entropy compression method
• Efficient recognition of rational relations
• Hopf algebra of permutation pattern functions (extended abstract)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1741092 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• Le calcul rapide des mélanges de deux mots. (Fast computing of the shuffle of two words)
• On recognizing words that are squares for the shuffle product
• On the complexity of iterated shuffle
• On the computational complexity of a merge recognition problem
• Pattern matching for separable permutations
• Precedence-Constrained Scheduling Problems Parameterized by Partial Order Width
• Shuffling and unshuffling
• Square-free shuffles of words
• The Shuffle Product: New Research Directions
• Unshuffling a square is NP-hard
• Unshuffling permutations

Cited in

(13)

• A simple proof that the \((n^{2} - 1)\)-puzzle is hard
• Unshuffling permutations: trivial bijections and compositions
• Unshuffling a square is NP-hard
• On shuffled-square-free words
• On recognising words that are squares for the shuffle product
• Unshuffling permutations
• On recognizing words that are squares for the shuffle product
• Subsequence covers of words
• Shuffle squares and reverse shuffle squares
• Shuffle squares and nest-free graphs
• The n-ary initial literal and literal shuffle
• Subsequence covers of words
• Matching probability between two aligned Markov dependent nucleic acid sequences while allowing d mutations. In honour of Joseph Glaz for his distinguished career and profound contributions to the field of applied probability and statistics

This page was built for publication: Recognizing binary shuffle squares is \textsf{NP}-hard

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