Algebraic foundations for qualitative calculi and networks

DOI10.1016/J.TCS.2019.02.033MaRDI QIDQ1733063zbMATH OpenOpenAlexWikidataFDO

Authors Marcel Jackson, Tomasz Kowalski, Robin Hirsch

Publication date 26 March 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.09140

zbMATH Keywords

constraint networknon-associative algebraqualitative calculusrelation algebrarepresentation

Mathematics Subject Classification ID

Logic in computer science (03B70) Cylindric and polyadic algebras; relation algebras (03G15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: A qualitative representation $phi$ is like an ordinary representation of a relation algebra, but instead of requiring $(a;b{)}^{p}hi=a^{p}hi|b^{p}hi$, as we do for ordinary representations, we only require that $c^{p}hisupseteq{a}^{p}hi|b^{p}hiiffcgeqa;b$, for each $c$ in the algebra. A constraint network is qualitatively satisfiable if its nodes can be mapped to elements of a qualitative representation, preserving the constraints. If a constraint network is satisfiable then it is clearly qualitatively satisfiable, but the converse can fail. However, for a wide range of relation algebras including the point algebra, the Allen Interval Algebra, RCC8 and many others, a network is satisfiable if and only if it is qualitatively satisfiable. Unlike ordinary composition, the weak composition arising from qualitative representations need not be associative, so we can generalise by considering network satisfaction problems over non-associative algebras. We prove that computationally, qualitative representations have many advantages over ordinary representations: whereas many finite relation algebras have only infinite representations, every finite qualitatively representable algebra has a finite qualitative representation; the representability problem for (the atom structures of) finite non-associative algebras is NP-complete; the network satisfaction problem over a finite qualitatively representable algebra is always in NP; the validity of equations over qualitative representations is co-NP-complete. On the other hand we prove that there is no finite axiomatisation of the class of qualitatively representable algebras.

Recommendations

• So, what exactly is a qualitative calculus?
• From points to intervals
• Weak Composition for Qualitative Spatial and Temporal Reasoning
• Finite unary relations and qualitative constraint satisfaction
• Tractable approximations for temporal constraint handling

Cites work

• A canonical model of the region connection calculus
• A finer reduction of constraint problems to digraphs
• A finite relation algebra with undecidable network satisfaction problem
• A relation-algebraic approach to the region connection calculus
• Boolean Algebras with Operators. Part I
• Combinatorial aspects of relations
• Combining qualitative and quantitative constraints in temporal reasoning
• scientific article; zbMATH DE number 5916930 (Why is no real title available?)
• scientific article; zbMATH DE number 47233 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1086671 (Why is no real title available?)
• scientific article; zbMATH DE number 6747941 (Why is no real title available?)
• Maintaining knowledge about temporal intervals
• Necessary subalgebras of simple nonintegral semiassociative relation algebras
• On binary constraint problems
• On the calculus of relations
• RCC8 binary constraint network can be consistently extended
• Relation algebras
• Relation algebras by games
• Relation algebras of intervals
• Representability is not decidable for finite relation algebras
• Representations of integral relation algebras
• Some Recent Results in Metric Temporal Logic
• Some Varieties Containing Relation Algebras
• Weak Composition for Qualitative Spatial and Temporal Reasoning

Cited in

(15)

• So, what exactly is a qualitative calculus?
• Relation algebras of Sugihara, Belnap, Meyer, and Church
• Weak Composition for Qualitative Spatial and Temporal Reasoning
• From points to intervals
• Expressive power and complexity in algebraic logic
• Finite unary relations and qualitative constraint satisfaction
• Minimality of combined qualitative constraint networks
• Hardness of Network Satisfaction for Relation Algebras with Normal Representations
• The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
• A Logic of East and West
• KI 2005: Advances in Artificial Intelligence
• FINITE RELATION ALGEBRAS
• Edge colourings and qualitative representations of chromatic algebras
• Network satisfaction problems solved by k-consistency
• On redundant topological constraints

This page was built for publication: Algebraic foundations for qualitative calculi and networks

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