Algebraic foundations for qualitative calculi and networks
This work addresses foundational issues in qualitative reasoning for AI and spatial/temporal reasoning, providing theoretical insights but is incremental in extending existing algebraic frameworks.
The paper tackles the problem of qualitative representations in relation algebras, showing that for many algebras like the Allen Interval Algebra and RCC8, network satisfiability is equivalent to qualitative satisfiability, and proves computational advantages such as finite qualitative representations for all finite algebras and NP-completeness for representability problems.
A qualitative representation $φ$ is like an ordinary representation of a relation algebra, but instead of requiring $(a; b)^φ= a^φ| b^φ$, as we do for ordinary representations, we only require that $c^φ\supseteq a^φ| b^φ\iff c\geq a ; 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.