Affine systems of equations and counting infinitary logic

DOI10.1016/J.TCS.2008.12.049zbMath1168.68040OpenAlexW1993886628WikidataQ58215545 ScholiaQ58215545MaRDI QIDQ1014638

Anuj Dawar, Albert Atserias, Andrei A. Bulatov

Publication date: 29 April 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.12.049

zbMATH Keywords

tame congruence theoryconstraint satisfaction problemuniversal algebrasystems of linear equationsfinite model theoryinexpressibilitybijective gameinfinitary logic with countingquantifier-free reductions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of universal algebra in computer science (08A70) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Model theory of finite structures (03C13) Other infinitary logic (03C75)

Related Items (21)

Choiceless Polynomial Time on Structures with Small Abelian Colour Classes ⋮ Equivariant algorithms for constraint satisfaction problems over coset templates ⋮ Is Polynomial Time Choiceless? ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ Quantum and non-signalling graph isomorphisms ⋮ Capturing the polynomial hierarchy by second-order revised Krom logic ⋮ Constructing Hard Examples for Graph Isomorphism ⋮ Proof Complexity Meets Algebra ⋮ RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC! ⋮ Unnamed Item ⋮ Inapproximability of unique games in fixed-point logic with counting ⋮ On the descriptive complexity of temporal constraint satisfaction problems ⋮ Consistency, acyclicity, and positive Semirings ⋮ Constraint satisfaction, graph isomorphism, and the pebbling comonad ⋮ On Weisfeiler-Leman invariance: subgraph counts and related graph properties ⋮ Definable Inapproximability: New Challenges for Duplicator ⋮ Choiceless Logarithmic Space ⋮ A Dichotomy for First-Order Reducts of Unary Structures ⋮ Unnamed Item ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Bounded width problems and algebras
• Consistency in networks of relations
• A restricted second order logic for finite structures
• Constraints and universal algebra
• Graph searching and a min-max theorem for tree-width
• Logical hierarchies in PTIME
• Networks of constraints: Fundamental properties and applications to picture processing
• Closed systems of functions and predicates
• Undirected ST-connectivity in log-space
• Structure and importance of logspace-MOD class
• The structure of finite algebras
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Closure properties of constraints
• On polynomial time computation over unordered structures
• Linear Datalog and Bounded Path Duality of Relational Structures
• Classifying the Complexity of Constraints Using Finite Algebras
• A Characterisation of First-Order Constraint Satisfaction Problems
• A Simple Algorithm for Mal'tsev Constraints

This page was built for publication: Affine systems of equations and counting infinitary logic