Qualitative spatial reasoning with topological information - Renz, Jochen (Berlin ; New York : Springer, 2002)
Introduction
Different Approaches for Representing Spatial Knowledge
Qualitative Spatial Representation and Reasoning
Applications and Research Goals of Qualitative Spatial Representation and Reasoning
Topological Relations as a Basis for Qualitative Spatial Representation and Reasoning
Overview of This Book. Background
Toplogy
Propositional and First-Order Logic
Propositional Modal Logics
First-Order Logic
Computational Complexity
Tractability and NP-Completeness
Phase Transitions
Constraint Satisfaction
Binary Constraint Satisfaction Problems and Relation Algebras
Relation Algebras Based on JEPD Relations
Temporal Reasoning with Allen's Interval Algebra. Qualitative Spatial Representation and Reasoning
History of Qualitative Spatial Reasoning
Principles of Qualitative Spatial Reasoning
Different Approaches to Qualitative Spatial Reasoning
Topology
Orientation
Distance. The Region Connection Calculus
A Spatial Logic Based on Regions and Connection
The Region Calculus RCC-8
Encoding of RCC-8 in Modal Logic
Egenhofer's Approach to Topological Spatial Relations. Cognitive Properties of Topological Spatial Relations
Psychological Background
Empirical Investigation I: Grouping Task with Circural Regions
Subjects, Method, and Procedure
Results of the Second Investigation
Discussion
Discussion and Outlook. Computational Properties of RCC-8
Computational Complexity of RCC-8
Transformation of RSAT to SAT
Analysis of the Modal Encoding
Determining a Particular Kripke Model
Transformation to a Classical Propositional Formula
Tractable Subsets of RCC-8
Identifying a Large Tractable Subset of RCC-8
Maximality of H8 with Respect of Tractability
Applicability of Path-Consistency
Applying Positive Unit Resolution to Path-Consistency
Path-Consistency for the Full Set of Tractable Relations
Finding a Consistent Scenario
Discussion. A Complete Analysis of Tractability in RCC-8
A General Method for Proving Tractability of Sets of Relations
Candidates for Maximal Tractable Subsets of RCC-8
A Complete Analysis of Tractability
Finding a Consistent Scenario II:
An Improved Algorithm for All Tractable Subsets
Applying the New Method to Allen's Interval Algebra
Discussion. Empirical Evaluation of Reasoning with RCC-8
Test Instances, Heuristics, and Measurements
Empirical Evaluation of the Heuristics
Orthogonal Combination of the Heuristics
Combining Heuristics for Solving Large Instances
Discussion. Representational Properties of RCC-8
A Canonical Model of RCC-8
A Toplogical Interpretations of the Canonical Model
RCC-8 Models and the Dimension of Space
Applicability of the Canonical Model
Determination of RCC-8 Models
Generating a Realization
Discussion. Conclusions
Summary of Contributions
Discussion & Future Research. Enumeration of the Relations of the Maximal Tractable Subsets of RCC-8
Relations of H8 and Their Abbreviated Form
Functional Construction of the Relations of H8 / H8 Using Relations of H8
The Maximal Tractable subsets of RCC-8. References. Index.
Includes bibliographical references (p. 191-200) and index.
Keywords: Knowledge representation (Information theory); Space perception