The complexity of constraint satisfaction problems for small relation algebras

DOI10.1016/J.ARTINT.2004.02.003zbMATH Open1085.68152OpenAlexW1978888415MaRDI QIDQ814599FDOQ814599

Authors: N. E. Zubov 

Publication date: 7 February 2006

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2004.02.003

Recommendations

• The complexity of constraint satisfaction: an algebraic approach
• The complexity of constraint satisfaction revisited
• scientific article; zbMATH DE number 1670830
• On computation complexity problems concerning relation algebras
• Publication:4729350
• Constraint satisfaction -- algorithms and complexity analysis
• Constraint satisfaction with succinctly specified relations
• Classifying the Complexity of Constraints Using Finite Algebras
• Universal algebra and hardness results for constraint satisfaction problems

zbMATH Keywords

Computational complexityConstraint satisfaction problemRelation algebra

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cylindric and polyadic algebras; relation algebras (03G15)

Cites Work

• Maintaining knowledge about temporal intervals
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Towards a general theory of action and time
• Temporal constraint networks
• Reasoning about temporal relations
• Boolean Algebras with Operators
• Title not available (Why is that?)
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• Relation algebras by games
• On binary constraint problems
• The origin of relation algebras in the development and axiomatization of the calculus of relations
• A relation-algebraic approach to the region connection calculus
• A necessary relation algebra for mereotopology
• A finite relation algebra with undecidable network satisfaction problem
• Expressive power and complexity in algebraic logic
• Twenty-one large tractable subclasses of Allen's algebra
• Small integral relation algebras generated by a partial order
• Determining consistency of topological relations
• Computational complexity of relating time points with intervals
• Representations for small relation algebras
• Tractable approximations for temporal constraint handling
• Algebras of approximating regions
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Temporal extension of Prolog
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Revision of defeasible preferences
• On computation complexity problems concerning relation algebras
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• Title not available (Why is that?)
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
• NP-completeness of small conflict set generation for congruence closure

This page was built for publication: The complexity of constraint satisfaction problems for small relation algebras

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q814599)