On binary constraint problems
From MaRDI portal
Publication:4305669
DOI10.1145/176584.176585zbMath0813.03045OpenAlexW2090310951MaRDI QIDQ4305669
Roger D. Maddux, Peter B. Ladkin
Publication date: 7 June 1995
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/176584.176585
algorithmsrelation algebrasbinary constraint satisfaction problemsmatrices of relationspath- consistency
Analysis of algorithms and problem complexity (68Q25) Knowledge representation (68T30) Cylindric and polyadic algebras; relation algebras (03G15)
Related Items (36)
On point-duration networks for temporal reasoning ⋮ Non-local configuration of component interfaces by constraint satisfaction ⋮ On point-based temporal disjointness ⋮ Spatial reasoning with rectangular cardinal relations. The convex tractable subalgebra ⋮ From points to intervals ⋮ Relation algebras of intervals ⋮ Hardness of Network Satisfaction for Relation Algebras with Normal Representations ⋮ An algebraic characterization of tractable constraints ⋮ A condensed semantics for qualitative spatial reasoning about oriented straight line segments ⋮ Qualitative reasoning about relative direction of oriented points ⋮ Relation algebras of Sugihara, Belnap, Meyer, and Church ⋮ Algebraic foundations for qualitative calculi and networks ⋮ RCC8 binary constraint network can be consistently extended ⋮ Incremental qualitative temporal reasoning: Algorithms for the point algebra and the ORD-Horn class ⋮ Temporal constraint networks ⋮ Tractable approximations for temporal constraint handling ⋮ Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class ⋮ Reasoning about qualitative temporal information ⋮ GNet: a generalized network model and its applications in qualitative spatial reasoning ⋮ Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure ⋮ A relation-algebraic approach to the region connection calculus ⋮ Combinatorial problems raised from 2-semilattices ⋮ Relation algebras and their application in temporal and spatial reasoning ⋮ Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning ⋮ So, what exactly is a qualitative calculus? ⋮ Probabilistic temporal networks: A unified framework for reasoning with time and uncertainty ⋮ Constraints, consistency and closure ⋮ On the algebraic structure of combinatorial problems ⋮ Relational proof systems for spatial reasoning ★ ⋮ Backtracking algorithms for disjunctions of temporal constraints ⋮ A new approach to cyclic ordering of 2D orientations using ternary relation algebras ⋮ Satisfying constraint sets through convex envelopes ⋮ Efficient algorithms for qualitative reasoning about time ⋮ The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom ⋮ Combining topological and size information for spatial reasoning ⋮ The complexity of constraint satisfaction problems for small relation algebras
This page was built for publication: On binary constraint problems
