Unshuffling a square is NP-hard
From MaRDI portal
Publication:2637646
Abstract: A shuffle of two strings is formed by interleaving the characters into a new string, keeping the characters of each string in order. A string is a square if it is a shuffle of two identical strings. There is a known polynomial time dynamic programming algorithm to determine if a given string z is the shuffle of two given strings x,y; however, it has been an open question whether there is a polynomial time algorithm to determine if a given string z is a square. We resolve this by proving that this problem is NP-complete via a many-one reduction from 3- Partition.
Recommendations
Cites work
- A P-complete language describable with iterated shuffle
- An algorithm for a merge recognition problem
- An approach to software system modelling and analysis
- Circuit complexity of shuffle
- Extending regular expressions with iterated shuffle
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1003236 (Why is no real title available?)
- Mappings of languages by two-tape devices
- 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
- On the expressive power of the shuffle operator matched with intersection by regular sets
- Shuffle languages are in P
- Shuffle languages, Petri nets, and context-sensitive grammars
- Shuffling and unshuffling
- Software Descriptions with Flow Expressions
- Structural properties of shuffle automata
- The power of synchronizing operations on strings
- The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
- Tight Bounds on the Descriptional Complexity of Regular Expressions
Cited in
(29)- Algorithmic and algebraic aspects of unshuffling permutations
- String shuffle: circuits and graphs
- Recognizing binary shuffle squares is \textsf{NP}-hard
- A formal framework for stringology
- Unshuffling permutations: trivial bijections and compositions
- On shuffled-square-free words
- On recognising words that are squares for the shuffle product
- The Shuffle Product: New Research Directions
- Circuit complexity of shuffle
- A constant time string shuffle algorithm on reconfigurable meshes
- Square-free words with square-free self-shuffles
- Infinite self-shuffling words
- Diverse Palindromic Factorization is NP-Complete
- Square-free shuffles of words
- scientific article; zbMATH DE number 7376042 (Why is no real title available?)
- Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
- Longest Common Subsequence with Gap Constraints
- Subsequence covers of words
- Subsequences in bounded ranges: matching and analysis problems
- Shuffle squares and reverse shuffle squares
- Combinatorial algorithms for subsequence matching: a survey
- Decision problems on copying and shuffling
- Subsequences with generalised gap constraints: upper and lower complexity bounds
- Shuffle squares and nest-free graphs
- The n-ary initial literal and literal shuffle
- Longest common subsequence with gap constraints
- Subsequence covers of words
- Subsequence matching and analysis problems for formal languages
- Linear time subsequence and supersequence regex matching
This page was built for publication: Unshuffling a square is NP-hard
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2637646)
