On the computational complexity of a merge recognition problem

DOI10.1016/0166-218X(83)90021-5zbMath0496.68028MaRDI QIDQ1170032

Anthony Mansfield

Publication date: 1983

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

polynomial time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (9)

Unshuffling a square is NP-hard ⋮ Unnamed Item ⋮ On recognising words that are squares for the shuffle product ⋮ 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 ⋮ Hardness of equivalence checking for composed finite-state systems ⋮ Reconstructing a history of recombinations from a set of sequences

Cites Work

• An algorithm for a merge recognition problem
• Unnamed Item

This page was built for publication: On the computational complexity of a merge recognition problem