RPO constraint solving is in NP

DOI10.1007/10703163_26MaRDI QIDQ4263810zbMATH OpenFDO

Authors Paliath Narendran, Michaël Rusinowitch, Rakesh M. Verma

Publication date 22 September 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/10703163_26

zbMATH Keywords

complexity classordering constraints

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42)

Recommendations

• Simple LPO constraint solving methods
• Practical algorithms for deciding path ordering constraint satisfaction.
• Solving simplification ordering constraints
• On recursive path ordering

Cited in

(5)

• Practical algorithms for deciding path ordering constraint satisfaction.
• Orienting rewrite rules with the Knuth-Bendix order.
• Rikudo is NP-complete
• Decision Procedures for Automating Termination Proofs
• KBO Constraint Solving Revisited

This page was built for publication: RPO constraint solving is in NP

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