Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
From MaRDI portal
Publication:269512
DOI10.1016/j.jcss.2016.03.002zbMath1338.68108arXiv1506.00479OpenAlexW2311963849MaRDI QIDQ269512
Publication date: 18 April 2016
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1506.00479
Related Items
Tropically convex constraint satisfaction ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Tractability conditions for numeric CSPs ⋮ Max-Closed Semilinear Constraint Satisfaction ⋮ Unnamed Item ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Computational complexity of linear constraints over the integers
- Colouring, constraint satisfaction, and complexity
- On the algebraic structure of combinatorial problems
- On the decidability of semilinearity for semialgebraic sets and its implications for spatial databases
- Corrigendum to: ``On the decidability of semilinearity for semialgebraic sets and its implications for spatial databases
- Convex polarities over ordered fields
- Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction
- Affine Consistency and the Complexity of Semilinear Constraints
- Essential Convexity and Complexity of Semi-Algebraic Constraints
- Constraint Satisfaction Problems over the Integers with Successor
- Non-dichotomies in Constraint Satisfaction Complexity
- The complexity of temporal constraint satisfaction problems
- A Decision Procedure for the First Order Theory of Real Addition with Order
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Model Theory
- Monotone monadic SNP and constraint satisfaction
- Classifying the Complexity of Constraints Using Finite Algebras
- The complexity of satisfiability problems
- Decidability of Definability
