Tractable combinations of temporal CSPs

MaRDI QIDQ5094139zbMATH OpenFDO

Authors Manuel Bodirsky, Johannes Greiner, Jakub Rydval

Publication date 2 August 2022

Full work available at URL https://arxiv.org/abs/2012.05682, https://lmcs.episciences.org/9609

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Recommendations

• The complexity of temporal constraint satisfaction problems
• Complexity of combinations of qualitative constraint satisfaction problems
• Discrete temporal constraint satisfaction problems
• scientific article; zbMATH DE number 7199580
• Tractable Quantified Constraint Satisfaction Problems over Positive Temporal Templates

Cites work

• A complexity dichotomy for poset constraint satisfaction
• A Proof of the Algebraic Tractability Conjecture for Monotone Monadic SNP
• Architecting Solvers for SAT Modulo Theories: Nelson-Oppen with DPLL
• Complexity of infinite-domain constraint satisfaction
• Complexity, convexity and combinations of theories
• Constraint satisfaction problems for reducts of homogeneous graphs
• Constraint Satisfaction with Countable Homogeneous Templates
• Cyclic ordering is NP-complete
• Disjunctions, independence, refinements
• Equivalence constraint satisfaction problems
• Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups
• scientific article; zbMATH DE number 1688811 (Why is no real title available?)
• scientific article; zbMATH DE number 44603 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1140675 (Why is no real title available?)
• scientific article; zbMATH DE number 1538017 (Why is no real title available?)
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• Model-theoretic methods in combined constraint satisfiability
• Permutations on the random permutation
• Reasoning about temporal relations
• Scheduling with AND/OR Precedence Constraints
• Simplification by Cooperating Decision Procedures
• Temporal constraint satisfaction problems in fixed-point logic
• The 42 reducts of the random ordered graph
• The complexity of equality constraint languages
• The complexity of phylogeny constraint satisfaction problems
• The complexity of temporal constraint satisfaction problems
• The reducts of equality up to primitive positive interdefinability
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
• Total Ordering Problem
• Tractability of quantified temporal constraints to the max
• Tractable combinations of theories via sampling
• Tractable set constraints
• Unions of non-disjoint theories and combinations of satisfiability procedures

Cited in

(6)

• The complexity of finding temporal separators under waiting time constraints
• Robust Approximation of Temporal CSP
• Efficient Temporal Satisfiability
• Tractable Combinations of Temporal CSPs
• Complexity classification transfer for CSPs via algebraic products
• A brief history of Timed CSP

This page was built for publication: Tractable combinations of temporal CSPs

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