On the computational complexity of a merge recognition problem

DOI10.1016/0166-218X(83)90021-5MaRDI QIDQ1170032zbMATH OpenFDO

Authors 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)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• An algorithm for a merge recognition problem

Cited in

(9)

• On recognising words that are squares for the shuffle product
• Algorithmic and algebraic aspects of unshuffling permutations
• String shuffle: circuits and graphs
• Reconstructing a history of recombinations from a set of sequences
• Recognizing binary shuffle squares is \textsf{NP}-hard
• Unshuffling a square is NP-hard
• The Shuffle Product: New Research Directions
• Hardness of equivalence checking for composed finite-state systems
• scientific article; zbMATH DE number 7376042 (Why is no real title available?)

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

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