Constraint satisfaction problems over the integers with successor

DOI10.1007/978-3-662-47672-7_21MaRDI QIDQ3448790zbMATH OpenOpenAlexFDO

Authors Manuel Bodirsky, Barnaby Martin, Antoine Mottet

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.08572, http://dro.dur.ac.uk/20040/1/20040.pdf

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70)

Abstract: A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) whose constraint language consists of relations that are first-order definable over $(BbbZ,<)$. Our main result says that every distance CSP is in Ptime or NP-complete, unless it can be formulated as a finite domain CSP in which case the computational complexity is not known in general.

Recommendations

• Discrete temporal constraint satisfaction problems
• Constraint satisfaction problems over numeric domains
• Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers.

Cites work

• scientific article; zbMATH DE number 2134000 (Why is no real title available?)
• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• Closure properties of constraints
• Computational complexity of linear constraints over the integers
• Constraint Satisfaction with Countable Homogeneous Templates
• Existence theorems for weakly symmetric operations
• Model Theory
• On the complexity of H-coloring
• On the scope of the universal-algebraic approach to constraint satisfaction
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The complexity of constraint satisfaction: an algebraic approach
• The complexity of equality constraint languages
• The complexity of temporal constraint satisfaction problems

Cited in

(13)

• Constraint Satisfaction Problems on Intervals and Lengths
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• scientific article; zbMATH DE number 7378350 (Why is no real title available?)
• MAX-closed semilinear constraint satisfaction
• Tropically convex constraint satisfaction
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• Circuit satisfiability and constraint satisfaction around Skolem arithmetic
• A dichotomy for first-order reducts of unary structures
• Constraint satisfaction problems over numeric domains
• The wonderland of reflections
• The language of stratified sets is confluent and strongly normalising
• \((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's
• Discrete temporal constraint satisfaction problems

This page was built for publication: Constraint satisfaction problems over the integers with successor

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