Qualitative Spatial and Temporal Reasoning

Gérard Ligozat held the position of Researcher in Mathematics and Computer Science at the CNRS, and was a Professor of Computer Science at the University of Paris-Sud, France. He was offered a professorship in computer science at Adam Mickiewicz University, Poznan, Poland, where he taught Artificial Intelligence in 2008. He has been working on the subject of qualitative temporal and spatial reasoning for the past 25 years.

• Introduction. Qualitative Reasoning xviiChapter 1. Allen’s Calculus 11.1. Introduction 11.2. Allen’s interval relations 61.3. Constraint networks 81.4. Constraint propagation 171.5. Consistency tests 26Chapter 2. Polynomial Subclasses of Allen’s Algebra 292.1. “Show me a tractable relation!” 292.2. Subclasses of Allen’s algebra 302.3. Maximal tractable subclasses of Allen’s algebra 522.4. Using polynomial subclasses 572.5. Models of Allen’s language 602.6. Historical note 61Chapter 3. Generalized Intervals 633.1. “When they built the bridge .  “ 633.2. Entities and relations 653.3. The lattice of basic (p, q)-relations 683.4. Regions associated with basic (p, q)-relations 693.5. Inversion and composition 733.6. Subclasses of relations: convex and pre-convex relations 793.7. Constraint networks 823.8. Tractability of strongly pre-convex relations 833.9. Conclusions 843.10. Historical note 85Chapter 4. Binary Qualitative Formalisms 874.1. “Night driving” 874.2. Directed points in dimension 1 924.3. Directed intervals 974.4. The OPRA direction calculi 994.5. Dipole calculi 1004.6. The Cardinal direction calculus 1014.7. The Rectangle calculus 1044.8. The n-point calculus 1064.9. The n-block calculus 1084.10. Cardinal directions between regions 1094.11. The INDU calculus 1234.12. The 2n-star calculi 1264.13. The Cyclic interval calculus 1284.14. The RCC–8 formalism 1314.15. A discrete RCC theory 137Chapter 5. Qualitative Formalisms of Arity Greater than 2 1455.1. “The sushi bar” 1455.2. Ternary spatial and temporal formalisms 1465.3. Alignment relations between regions 1555.4. Conclusions 158Chapter 6. Quantitative Formalisms, Hybrids, and Granularity 1596.1. “Did John meet Fred this morning?”1596.2. TCSP metric networks 1606.3. Hybrid networks 1646.4. Meiri’s formalism 1686.5. Disjunctive linear relations (DLR) 1746.6. Generalized temporal networks 1756.7. Networks with granularity 179Chapter 7. Fuzzy Reasoning 1877.1. “Picasso’s Blue period” 1877.2. Fuzzy relations between classical intervals 1887.3. Events and fuzzy intervals 1957.4. Fuzzy spatial reasoning: a fuzzy RCC 2087.5. Historical note 222Chapter 8. The Geometrical Approach and Conceptual Spaces 2238.1. “What color is the chameleon?” 2238.2. Qualitative semantics 2248.3. Why introduce topology and geometry? 2258.4. Conceptual spaces 2268.5. Polynomial relations of INDU 2378.6. Historical note 258Chapter 9. Weak Representations 2599.1. “Find the hidden similarity” 2599.2. Weak representations 2619.3. Classifying the weak representations of An 2759.4. Extension to the calculi based on linear orders 2839.5. Weak representations and configurations 2909.6. Historical note 304Chapter 10. Models of RCC−8 30510.1. “Disks in the plane” 30510.2. Models of a composition table 30710.3. The RCC theory and its models 31210.4. Extensional entries of the composition table 31910.5. The generalized RCC theory 32910.6. A countable connection algebra 33710.7. Conclusions 341Chapter 11. A Categorical Approach of Qualitative Reasoning 34311.1. “Waiting in line” 34311.2. A general construction of qualitative formalisms 34611.3. Examples of partition schemes 34911.4. Algebras associated with qualitative formalisms 35011.5. Partition schemes and weak representations 35211.6. A general definition of qualitative formalisms 35311.7. Interpretating consistency 35511.8. The category of weak representations 35711.9. Conclusions 360Chapter 12. Complexity of Constraint Languages 36312.1. “Sudoku puzzles” 36312.2. Structure of the chapter 36512.3. Constraint languages 36612.4. An algebraic approach of complexity 36712.5. CSPs and morphisms of relational structures 36812.6. Clones of operations 37312.7. From local consistency to global consistency 37512.8. The infinite case 37612.9. Disjunctive constraints and refinements 38212.10. Refinements and independence 38912.11. Historical note 390Chapter 13. Spatial Reasoning and Modal Logic 39113.1. “The blind men and the elephant” 39113.2. Space and modal logics 39313.3. The modal logic S4 39313.4. Topological models 39613.5. Translating the RCC−8 predicates 40813.6. An alternative modal translation of RCC−8 40913.7. Generalized frames 41013.8. Complexity 41113.9. Complements 412Chapter 14. Applications and Software Tools 41314.1. Applications 41314.2. Software tools 416Chapter 15. Conclusion and Prospects 42315.1. Introduction 42315.2. Combining qualitative formalisms 42315.3. Spatio-temporal reasoning 42615.4. Alternatives to qualitative reasoning 43015.5. To conclude — for good 434Appendix A. Elements of Topology 435A.1. Topological spaces 435A.2. Metric spaces 445A.3. Connectedness and convexity 447Appendix B. Elements of Universal Algebra 451B.1. Abstract algebras 451B.2. Boolean algebras 452B.3. Binary relations and relation algebras 454B.4. Basic elements of the language of categories 457Appendix C. Disjunctive Linear Relations 463C.1. DLRs: definitions and satisfiability 463C.2. Linear programming 464C.3. Complexity of the satisfiability problem 466Bibliography 471Index 501