Unshuffling a square is NP-hard

DOI10.1016/j.jcss.2013.11.002zbMath1285.68130arXiv1211.7161OpenAlexW2163733217MaRDI QIDQ2637646

Samuel R. Buss, Michael Soltys

Publication date: 13 February 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1211.7161

zbMATH Keywords

NP-completenesssquare shuffle

Mathematics Subject Classification ID

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

Related Items (19)

Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Square-free words with square-free self-shuffles ⋮ On shuffled-square-free words ⋮ Longest Common Subsequence with Gap Constraints ⋮ Subsequence covers of words ⋮ Unnamed Item ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Shuffle squares and reverse shuffle squares ⋮ On the complexity and decidability of some problems involving shuffle ⋮ On recognising words that are squares for the shuffle product ⋮ Infinite self-shuffling words ⋮ Unnamed Item ⋮ Square-free shuffles of words ⋮ Diverse Palindromic Factorization is NP-Complete ⋮ 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 ⋮ A formal framework for stringology

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of iterated shuffle
• Extending regular expressions with iterated shuffle
• The power of synchronizing operations on strings
• An algorithm for a merge recognition problem
• On the computational complexity of a merge recognition problem
• A P-complete language describable with iterated shuffle
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• Shuffle languages are in P
• Structural properties of shuffle automata
• Circuit Complexity of Shuffle
• Tight Bounds on the Descriptional Complexity of Regular Expressions
• Shuffle languages, Petri nets, and context-sensitive grammars
• Software Descriptions with Flow Expressions
• An approach to software system modelling and analysis
• On the expressive power of the shuffle operator matched with intersection by regular sets
• On Recognizing Words That Are Squares for the Shuffle Product
• Mappings of languages by two-tape devices

This page was built for publication: Unshuffling a square is NP-hard