The complexity of constraint satisfaction problems for small relation algebras
From MaRDI portal
Publication:814599
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)
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
Cites work
- scientific article; zbMATH DE number 3933071 (Why is no real title available?)
- scientific article; zbMATH DE number 44603 (Why is no real title available?)
- scientific article; zbMATH DE number 67019 (Why is no real title available?)
- scientific article; zbMATH DE number 67035 (Why is no real title available?)
- scientific article; zbMATH DE number 3571502 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1149443 (Why is no real title available?)
- scientific article; zbMATH DE number 1149445 (Why is no real title available?)
- scientific article; zbMATH DE number 1373583 (Why is no real title available?)
- A Temporal extension of Prolog
- A finite relation algebra with undecidable network satisfaction problem
- A necessary relation algebra for mereotopology
- A relation-algebraic approach to the region connection calculus
- Algebras of approximating regions
- Boolean Algebras with Operators
- Computational complexity of relating time points with intervals
- Determining consistency of topological relations
- Expressive power and complexity in algebraic logic
- Maintaining knowledge about temporal intervals
- On binary constraint problems
- On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
- Reasoning about temporal relations
- Relation algebras by games
- Representations for small relation algebras
- Small integral relation algebras generated by a partial order
- Temporal constraint networks
- The origin of relation algebras in the development and axiomatization of the calculus of relations
- Towards a general theory of action and time
- Tractable approximations for temporal constraint handling
- Twenty-one large tractable subclasses of Allen's algebra
Cited in
(8)- On computation complexity problems concerning relation algebras
- The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
- NP-completeness of small conflict set generation for congruence closure
- Revision of defeasible preferences
- Hardness of Network Satisfaction for Relation Algebras with Normal Representations
- scientific article; zbMATH DE number 1113997 (Why is no real title available?)
- On the Parameterized Complexity of Finding Small Unsatisfiable Subsets of CNF Formulas and CSP Instances
- Finite relation algebras with normal representations
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)
