On tractability and congruence distributivity

DOI10.2168/LMCS-3(2:6)2007zbMath1128.08004OpenAlexW2156285174MaRDI QIDQ5310691

Emil W. Kiss, Matthew A. Valeriote

Publication date: 11 October 2007

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2168/lmcs-3(2:6)2007

zbMATH Keywords

constraint satisfactioncongruence distributive varietytractabilityconstraint languagebounded relational widthJonsson term

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) Congruence modularity, congruence distributivity (08B10)

Related Items (9)

Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ Unnamed Item ⋮ Majority constraints have bounded pathwidth duality ⋮ Quantified Constraint Satisfaction and the Polynomially Generated Powers Property ⋮ Quantified constraint satisfaction and the polynomially generated powers property ⋮ Relation identities in 3-distributive varieties ⋮ There are no pure relational width 2 constraint satisfaction problems ⋮ Congruence modularity implies cyclic terms for finite algebras ⋮ Dualities for Constraint Satisfaction Problems

This page was built for publication: On tractability and congruence distributivity