scientific article; zbMATH DE number 7378350

DOI10.4230/LIPIcs.MFCS.2018.33MaRDI QIDQ5005133

Manuel Bodirsky, Barnaby Martin, Antoine Mottet, Marcello Mamino

Publication date: 4 August 2021

Full work available at URL: https://arxiv.org/abs/1807.00985

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

computational complexityconstraint satisfactionPresburger arithmetic

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

\((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distance constraint satisfaction problems
• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• Computational complexity of linear constraints over the integers
• Tropically convex constraint satisfaction
• The wonderland of reflections
• Computing Hermite and Smith normal forms of triangular integer matrices
• Schaefer's Theorem for Graphs
• Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction
• A linear space algorithm for computing the hermite normal form
• Essential Convexity and Complexity of Semi-Algebraic Constraints
• Constraint Satisfaction Problems over the Integers with Successor
• The complexity of temporal constraint satisfaction problems
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• Algorithms for the Solution of Systems of Linear Diophantine Equations
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Discrete Temporal Constraint Satisfaction Problems
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• Model Theory
• A Proof of the CSP Dichotomy Conjecture
• The complexity of satisfiability problems

This page was built for publication: