A Dichotomy for First-Order Reducts of Unary Structures

DOI10.23638/LMCS-14(2:13)2018zbMath1476.03041arXiv1601.04520MaRDI QIDQ4643958

Manuel Bodirsky, Antoine Mottet

Publication date: 30 May 2018

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Operations and polynomials in algebraic structures, primal algebras (08A40) Model theory of denumerable and separable structures (03C15)

Related Items

\((\mathbb{Z},\mathrm{succ},U)\), \((\mathbb{Z},E,U)\), and their CSP's, General lower bounds and improved algorithms for infinite-domain CSPs, Permutation groups with small orbit growth, Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems), PROJECTIVE CLONE HOMOMORPHISMS, Using model theory to find decidable and tractable description logics with concrete domains

Cites Work

• Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• Point algebras for temporal reasoning: Algorithms and complexity
• The complexity of equality constraint languages
• Existence theorems for weakly symmetric operations
• Affine systems of equations and counting infinitary logic
• The wonderland of reflections
• Datalog and constraint satisfaction with infinite templates
• Characterizations of several Maltsev conditions.
• Constraints, MMSNP and expander relational structures
• Schaefer's Theorem for Graphs
• Automata theory in nominal sets
• Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
• Rewritability in Monadic Disjunctive Datalog, MMSNP, and Expressive Description Logics (Invited Talk).
• Constraint Satisfaction Problems over the Integers with Successor
• The complexity of temporal constraint satisfaction problems
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• On free actions, minimal flows, and a problem by Ellis
• Closure properties of constraints
• The Complexity of Phylogeny Constraint Satisfaction
• Turing machines with atoms, constraint satisfaction problems, and descriptive complexity
• Locally Finite Constraint Satisfaction Problems
• The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction Problems
• A complexity dichotomy for poset constraint satisfaction
• A Proof of the CSP Dichotomy Conjecture
• Constraint Satisfaction Problems of Bounded Width
• Turing Machines with Atoms
• Cores of Countably Categorical Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• Decidability of Definability
• Topological Birkhoff
• Principles and Practice of Constraint Programming – CP 2003
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item