OMITTING TYPES, BOUNDED WIDTH AND THE ABILITY TO COUNT

DOI10.1142/S021819670900524XzbMath1178.68289MaRDI QIDQ3398315

Benoit Larose, László Zádori, Matthew A. Valeriote

Publication date: 28 September 2009

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

zbMATH Keywords

monotone circuits; variety; constraint satisfaction problems; bounded width; Hobby-McKenzie types

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

08B05: Equational logic, Mal'tsev conditions

08A72: Fuzzy algebraic structures

Related Items

Unnamed Item, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Dualities for Constraint Satisfaction Problems, The smallest hard trees, The algebraic structure of the densification and the sparsification tasks for CSPs, A new line of attack on the dichotomy conjecture, On the CSP Dichotomy Conjecture, Constraint Satisfaction Problems Solvable by Local Consistency Methods

Cites Work

• Unnamed Item
• On the expressive power of Datalog: tools and a case study.
• Bounded width problems and algebras
• Universal algebra and hardness results for constraint satisfaction problems
• Lower bounds on monotone complexity of the logical permanent
• The set of types of a finitely generated variety
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Recent Results on the Algebraic Approach to the CSP
• Dualities for Constraint Satisfaction Problems