Cover -- Qualitative Spatial and Temporal Reasoning -- Title Page -- Copyright Page -- Table of Contents -- Introduction. Qualitative Reasoning -- Chapter 1. Allen's Calculus -- 1.1. Introduction -- 1.1.1. "The mystery of the dark room" -- 1.1.2. Contributions of Allen's formalism -- 1.2. Allen's interval relations -- 1.2.1. Basic relations -- 1.2.2. Disjunctive relations -- 1.3. Constraint networks -- 1.3.1. Definition -- 1.3.2. Expressiveness -- 1.3.3. Consistency -- 1.4. Constraint propagation -- 1.4.1. Operations: inversion and composition -- 1.4.2. Composition table -- 1.4.3. Allen's algebra -- 1.4.4. Algebraic closure -- 1.4.5. Enforcing algebraic closure -- 1.5. Consistency tests -- 1.5.1. The case of atomic networks -- 1.5.2. Arbitrary networks -- 1.5.3. Determining polynomial subsets -- Chapter 2. Polynomial Subclasses of Allen's Algebra -- 2.1. "Show me a tractable relation!" -- 2.2. Subclasses of Allen's algebra -- 2.2.1. A geometrical representation of Allen's relations -- 2.2.2. Interpretation in terms of granularity -- 2.2.3. Convex and pre-convex relations -- 2.2.4. The lattice of Allen's basic relations -- 2.2.5. Tractability of convex relations -- 2.2.6. Pre-convex relations -- 2.2.7. Polynomiality of pre-convex relations -- 2.2.8. ORD-Horn relations -- 2.3. Maximal tractable subclasses of Allen's algebra -- 2.3.1. An alternative characterization of pre-convex relations -- 2.3.2. The other maximal polynomial subclasses -- 2.4. Using polynomial subclasses -- 2.4.1. Ladkin and Reinefeld's algorithm -- 2.4.2. Empirical study of the consistency problem -- 2.5. Models of Allen's language -- 2.5.1. Representations of Allen's algebra -- 2.5.2. Representations of the time-point algebra -- 2.5.3. ℵ0-categoricity of Allen's algebra -- 2.6. Historical note -- Chapter 3. Generalized Intervals -- 3.1. "When they built the bridge".

3.1.1. Towards generalized intervals -- 3.2. Entities and relations -- 3.3. The lattice of basic (p, q)-relations -- 3.4. Regions associated with basic (p, q)-relations -- 3.4.1. Associated polytopes -- 3.4.2. M-convexity of the basic relations -- 3.5. Inversion and composition -- 3.5.1. Inversion -- 3.5.2. Composition -- 3.5.3. The algebras of generalized intervals -- 3.6. Subclasses of relations: convex and pre-convex relations -- 3.6.1. (p, q)-relations -- 3.6.2. Convex relations -- 3.6.3. Pre-convex relations -- 3.7. Constraint networks -- 3.8. Tractability of strongly pre-convex relations -- 3.8.1. ORD-Horn relations -- 3.9. Conclusions -- 3.10. Historical note -- Chapter 4. Binary Qualitative Formalisms -- 4.1. "Night driving" -- 4.1.1. Parameters -- 4.1.2. A panorama of the presented formalisms -- 4.2. Directed points in dimension 1 -- 4.2.1. Operations -- 4.2.2. Constraint networks -- 4.2.3. Networks reducible to point networks -- 4.2.4. Arbitrary directed point networks -- 4.3. Directed intervals -- 4.3.1. Operations -- 4.3.2. Constraint networks and complexity -- 4.4. The OPRA direction calculi -- 4.5. Dipole calculi -- 4.6. The Cardinal direction calculus -- 4.6.1. Convex and pre-convex relations -- 4.6.2. Complexity -- 4.7. The Rectangle calculus -- 4.7.1. Convex and pre-convex relations -- 4.7.2. Complexity -- 4.8. The n-point calculus -- 4.8.1. Convexity and pre-convexity -- 4.9. The n-block calculus -- 4.9.1. Convexity and pre-convexity -- 4.10. Cardinal directions between regions -- 4.10.1. Basic relations -- 4.10.2. Operations -- 4.10.3. Consistency of basic networks -- 4.10.4. Applications of the algorithm -- 4.11. The INDU calculus -- 4.11.1. Inversion and composition -- 4.11.2. The lattice of INDU relations -- 4.11.3. Regions associated with INDU relations -- 4.11.4. A non-associative algebra -- 4.12. The 2n-star calculi.

4.12.1. Inversion and composition -- 4.13. The Cyclic interval calculus -- 4.13.1. Convex and pre-convex relations -- 4.13.2. Complexity of the consistency problem -- 4.14. The RCC-8 formalism -- 4.14.1. Basic relations -- 4.14.2. Allen's relations and RCC−8 relations -- 4.14.3. Operations -- 4.14.4. Maximal polynomial classes of RCC−8 -- 4.15. A discrete RCC theory -- 4.15.1. Introduction -- 4.15.2. Entities and relations -- 4.15.3. Mereology -- 4.15.4. Concept of contact and RCC−8 relations -- 4.15.5. Closure, interior and boundary -- 4.15.6. Self-connectedness -- 4.15.7. Paths, distance, and arc-connectedness -- 4.15.8. Distance between regions -- 4.15.9. Conceptual neighborhoods -- Chapter 5. Qualitative Formalisms of Arity Greater than 2 -- 5.1. "The sushi bar" -- 5.2. Ternary spatial and temporal formalisms -- 5.2.1. General concepts -- 5.2.2. The Cyclic point calculus -- 5.2.3. The Double-cross calculus -- 5.2.4. The Flip-flop and LR calculi -- 5.2.5. Practical and natural calculi -- 5.2.6. The consistency problem -- 5.3. Alignment relations between regions -- 5.3.1. Alignment between regions of the plane: the 5-intersection calculus -- 5.3.2. Ternary relations between solids in space -- 5.3.3. Ternary relations on the sphere -- 5.4. Conclusions -- Chapter 6. Quantitative Formalisms, Hybrids, and Granularity -- 6.1. "Did John meet Fred this morning?" -- 6.1.1. Contents of the chapter -- 6.2. TCSP metric networks -- 6.2.1. Operations -- 6.2.2. The consistency problem -- 6.3. Hybrid networks -- 6.3.1. Kautz and Ladkin's formalism -- 6.4. Meiri's formalism -- 6.4.1. Temporal entities and relations -- 6.4.2. Constraint networks -- 6.4.3. Constraint propagation -- 6.4.4. Tractability issues -- 6.5. Disjunctive linear relations (DLR) -- 6.5.1. A unifying formalism -- 6.5.2. Allen's algebra with constraints on durations -- 6.5.3. Conclusions.

6.6. Generalized temporal networks -- 6.6.1. Motivations -- 6.6.2. Definition of GTN -- 6.6.3. Expressiveness -- 6.6.4. Constraint propagation -- 6.6.5. Conclusions -- 6.7. Networks with granularity -- 6.7.1. Introduction -- 6.7.2. Granularities and granularity systems -- 6.7.3. Constraint networks -- 6.7.4. Complexity of the consistency problem -- 6.7.5. Propagation algorithms -- Chapter 7. Fuzzy Reasoning -- 7.1. "Picasso's Blue period" -- 7.2. Fuzzy relations between classical intervals -- 7.2.1. Motivations -- 7.2.2. The fuzzy Point algebra -- 7.2.3. The fuzzy Interval algebra -- 7.2.4. Fuzzy constraint networks -- 7.2.5. Algorithms, tractable subclasses -- 7.2.6. Assessment -- 7.3. Events and fuzzy intervals -- 7.3.1. Fuzzy intervals and fuzzy relations -- 7.3.2. Fuzzy constraints -- 7.3.3. An example of application -- 7.3.4. Complexity -- 7.3.5. Weak logical consequence -- 7.3.6. Assessment -- 7.4. Fuzzy spatial reasoning: a fuzzy RCC -- 7.4.1. Motivations -- 7.4.2. Fuzzy regions -- 7.4.3. Fuzzy RCC relations -- 7.4.4. Fuzzy RCC formulas -- 7.4.5. Semantics -- 7.4.6. Satisfying a finite set of normalized formulas -- 7.4.7. (n -- α, β)-models -- 7.4.8. Satisfiability and linear programming -- 7.4.9. Models with a finite number of degrees -- 7.4.10. Links with the egg-yolk calculus -- 7.5. Historical note -- Chapter 8. The Geometrical Approach and Conceptual Spaces -- 8.1. "What color is the chameleon?" -- 8.2. Qualitative semantics -- 8.3. Why introduce topology and geometry? -- 8.4. Conceptual spaces -- 8.4.1. Higher order properties and relations -- 8.4.2. Notions of convexity -- 8.4.3. Conceptual spaces associated to generalized intervals -- 8.4.4. The conceptual space associated to directed intervals -- 8.4.5. Conceptual space associated with cyclic intervals -- 8.4.6. Conceptual neighborhoods in Allen's relations.

8.4.7. Dominance spaces and dominance diagrams -- 8.5. Polynomial relations of INDU -- 8.5.1. Consistency -- 8.5.2. Convexity and Horn clauses -- 8.5.3. Pre-convex relations -- 8.5.4. NP-completeness of pre-convex relations -- 8.5.5. Strongly pre-convex relations -- 8.5.6. The subclass G -- 8.5.7. A summary of complexity results for INDU -- 8.6. Historical note -- Chapter 9. Weak Representations -- 9.1. "Find the hidden similarity" -- 9.2. Weak representations -- 9.2.1. Weak representations of the point algebra -- 9.2.2. Weak representations of Allen's interval algebra -- 9.2.3. Weak representations of the n-interval algebra -- 9.2.4. Constructing the canonical configuration -- 9.3. Classifying the weak representations of An -- 9.3.1. The category of weak representations of An -- 9.3.2. Reinterpretating the canonical construction -- 9.3.3. The canonical construction as adjunction -- 9.4. Extension to the calculi based on linear orders -- 9.4.1. Configurations -- 9.4.2. Description languages and associated algebras -- 9.4.3. Canonical constructions -- 9.4.4. The construction in the case of A Pointsn -- 9.5. Weak representations and configurations -- 9.5.1. Other qualitative formalisms -- 9.5.2. A non-associative algebra: INDU -- 9.5.3. Interpreting Allen's calculus on the integers -- 9.5.4. Algebraically closed but inconsistent scenarios: the case of cyclic intervals -- 9.5.5. Weak representations of RCC−8 -- 9.5.6. From weak representations to configurations -- 9.5.7. Finite topological models -- 9.5.8. Models in Euclidean space -- 9.6. Historical note -- Chapter 10. Models of RCC−8 -- 10.1. "Disks in the plane" -- 10.2. Models of a composition table -- 10.2.1. Complements on weak representations -- 10.2.2. Properties of weak representations -- 10.2.3. Models of the composition table of RCC−8 -- 10.3. The RCC theory and its models.

10.3.1. Composition tables relative to a logical theory.