Polynomial time termination and constraint satisfaction tests

DOI10.1007/978-3-662-21551-7_30zbMATH Open1503.68147OpenAlexW1589342712MaRDI QIDQ5055810FDOQ5055810

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

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

Mathematics Subject Classification ID

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

Cites Work

• Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
• Title not available (Why is that?)
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• 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 \(\lambda\)-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)