The complexity of constraint satisfaction problems for small relation algebras

DOI10.1016/j.artint.2004.02.003zbMath1085.68152OpenAlexW1978888415MaRDI QIDQ814599

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

zbMATH Keywords

Computational complexityConstraint satisfaction problemRelation algebra

Mathematics Subject Classification ID

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

Related Items (3)

Hardness of Network Satisfaction for Relation Algebras with Normal Representations ⋮ Revision of defeasible preferences ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom

Cites Work

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

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