Polynomial time termination and constraint satisfaction tests

DOI10.1007/978-3-662-21551-7_30MaRDI QIDQ5055810zbMATH OpenOpenAlexFDO

Authors David A. Plaisted

Publication date 9 December 2022

Published in Rewriting Techniques and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-21551-7_30

Mathematics Subject Classification ID

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

Recommendations

• Comparing CSP and SAT solvers for polynomial constraints in termination provers
• Polynomially solvable satisfiability problems
• Polynomial-average-time satisfiability problems
• CNF-Satisfiability Test by Counting and Polynomial Average Time
• Algorithms for testing satisfiability formulas
• Parameterized complexity of constraint satisfaction problems
• scientific article; zbMATH DE number 2018591
• Constraint satisfaction -- algorithms and complexity analysis
• Computational Complexity of Constraint Satisfaction

Cites work

• scientific article; zbMATH DE number 176755 (Why is no real title available?)
• scientific article; zbMATH DE number 1348468 (Why is no real title available?)
• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture

Cited in

(13)

• Algorithms and reductions for rewriting problems. II.
• Perpetuality and uniform normalization in orthogonal rewrite systems
• First-order theory of rewriting for linear variable-separated rewrite systems: automation, formalization, certification
• scientific article; zbMATH DE number 176755 (Why is no real title available?)
• Deciding confluence and normal form properties of ground term rewrite systems efficiently
• Recurrence with affine level mappings is P-time decidable for CLP
• Deciding Polynomial Termination Complexity for VASS Programs
• Perpetual reductions in -calculus
• On the longest perpetual reductions in orthogonal expression reduction systems
• Jumping and escaping: modular termination and the abstract path ordering
• Solving simplification ordering constraints
• Comparing CSP and SAT solvers for polynomial constraints in termination provers
• Natural termination

This page was built for publication: Polynomial time termination and constraint satisfaction tests

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