The STO problem is NP-complete

DOI10.1006/JSCO.1998.0249MaRDI QIDQ1284283zbMATH OpenOpenAlexFDO

Authors Piotr Krysta, Leszek Pacholski

Publication date 25 May 2000

Published in Journal of Symbolic Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/1967ac9560577ec514a1c9417dcd9add484e957f

Mathematics Subject Classification ID

Logic programming (68N17)

Recommendations

• The STO-problem is NP-hard
• scientific article; zbMATH DE number 4049047
• Rewriting Techniques and Applications
• Complexity of unification problems with associative-commutative operators
• Complexity of matching problems

Cited in

(5)

• Tatamibari is NP-complete
• LaserTank is NP-Complete
• The shortest common nonsubsequence problem is NP-complete
• Rikudo is NP-complete
• The STO-problem is NP-hard

This page was built for publication: The STO problem is NP-complete

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