A Complete Classification of Tractability in RCC-5
Journal of Artificial Intelligence ResearchPublished 1 June 1997Open access
Thomas Drakengren, Peter Jönsson
Citations70
SJR quartileQ1
SJR score1.37
SNIP2.97
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work investigates the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework for spatial reasoning and identifies all maximal tractable subalgebras which are four in total.
Abstract
We investigate the computational properties of the spatial algebra RCC-5 which is a restricted version of the RCC framework for spatial reasoning. The satisfiability problem for RCC-5 is known to be NP-complete but not much is known about its approximately four billion subclasses. We provide a complete classification of satisfiability for all these subclasses into polynomial and NP-complete respectively. In the process, we identify all maximal tractable subalgebras which are four in total.
Keywords
Computer Science
The complexity of theorem-proving procedures
6,107 Citations1971Stephen Cook
It is shown that any recognition problem solved by a polynomial time-bounded nondeterministic Turing machine can be “reduced” to the problem of determining whether a given propositional formula is a tautology.
A Spatial Logic based on Regions and Connection.
1,927 Citations1992David Randell, Zhanfeng Cui +1 more
An interval logic for reasoning about space is described, which supports a simpler ontology, has fewer functions and relations, yet does not su(cid:11)er in terms of its useful expressiveness.
Lecture notes in computer scienceReasoning about binary topological relations
625 Citations1991Max J. Egenhofer
A new formalism is presented to reason about topological relations based upon the nine intersections of boundaries, interiors, and complements between two objects that is applicable as a foundation for an algebra over topological Relations.
Journal of the ACMReasoning about temporal relations
407 Citations1995Bernhard Nebel, Hans-Jürgen Bürckert
Using an extensive machine-generated case analysis, it is shown that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P ≠ NP).
North-Holland mathematics studiesTopological Algebras Selected Topics
295 Citations1986
Topological Algebras with Involution, Representation Theory, and Generalized Spectra in the Presence of Approximate Identities.
Artificial IntelligenceReasoning about qualitative temporal information
274 Citations1992Peter van Beek
This paper defines computationally efficient procedures for solving two related reasoning tasks that arise in interval and point algebras: Given (possibly indefinite) knowledge of the relationships between some intervals or points, find one or more scenarios that are consistent with the information provided, and find all the feasible relations between every pair of interval or points.
Theoretical Computer ScienceIntuitionistic propositional logic is polynomial-space complete
233 Citations1979Richard Statman
It is shown that the question of whether a given propositional formula is intuitionistically valid (in Brouwer's sense, in Kripke's sense), or just provable by Heyting's rules, is p-space complete.
Principles of Knowledge Representation and ReasoningSpatial Reasoning with Propositional Logics
163 Citations1994Brandon Bennett
By encoding spatial relationships in a propositional representation automated reasoning becomes more effective, and specifies representations in both classical and intuitionistic propositional logic, which provide for efficient reasoning about a large class of spatial relations.
Modelling topological and metrical properties in physical processes
141 Citations1989David Randell, Anthony G. Cohn
The power of the formalism is illustrated by modelling the process of phagocytosis of theamoeba, together with an outline of how many pro-perties of physical entities and relations can be modelled within a unitary framework.
Topological inference
132 Citations1995Michelangelo Grigni, Dimitris Papadias +1 more
The MIT Press eBooksReasoning about qualitative temporal information
71 Citations1994Peter van Beek
This paper develops an O(n2)-time algorithm for finding one consistent scenario that is an 0(n) improvement over the previously known algorithm, and develops an algorithms for finding all the feasible relations that is of far more practical use than the previouslyknown algorithm.
Reasoning about temporal relations : a maximal tractable subclass of Allen's interval algebra
56 Citations1993Bernhard Nebel, Hans-Jürgen Bürckert
Lecture notes in computer scienceComputational properties of qualitative spatial reasoning: First results
50 Citations1995Bernhard Nebel
This paper focuses on the so-called RCC approach and uses Bennett's encoding of spatial reasoning in intuitionistic logic in order to show that consistency checking for the topological base relations can be done efficiently and proves path-consistency is sufficient for deciding global consistency.
Artificial IntelligenceOn the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
44 Citations1999Jochen Renz, Bernhard Nebel
It is proved that reasoning is NP-complete in general and identified a maximal tractable subset of the relations in RCC-8 that contains all base relations and shows that for this subset path-consistency is sufficient for deciding consistency.
Morgan Kaufmann Publishers eBooksPrinciples of knowledge representation and reasoning : proceedings of the fourth international conference (KR'94), Bonn, Germany, May 24-27, 1994
21 Citations1994Jon Doyle, Erik Sandewall +1 more
The proceedings of KR '94 comprise 55 papers on topics including deduction an search, description logics, theories of knowledge and belief, nonmonotonic reasoning and belief revision, action and time, planning and decision-making and reasoning about the physical world.
National Conference on Artificial IntelligenceMaximal tractable subclasses of Allen's interval algebra: preliminary report
19 Citations1996Thomas Drakengren, Peter Jönsson
This paper continues Nebel and Burckert's investigation of Allen's interval algebra by presenting nine more maximal tractable subclasses of the algebra (provided that P ≠ N P), in addition to their previously reported ORD-Horn subclass.
PubMedUsing interval logic for order assembly.
7 Citations1994Zhanfeng Cui
This paper presents and discusses a deductive and object-oriented data model based on a spatial-temporal logic where the concepts of metric information, local orientation and uncertainty are merged, and believes that this integrated formalism provides a formal basis for designing a declarative query language.