Wiley.com
Print this page Share

Qualitative Spatial and Temporal Reasoning

ISBN: 978-1-84821-252-7
544 pages
December 2011, Wiley-ISTE
Qualitative Spatial and Temporal Reasoning (1848212526) cover image

Description

Starting with an updated description of Allen's calculus, the book proceeds with a description of the main qualitative calculi which have been developed over the last two decades.  It describes the connection of complexity issues to geometric properties. Models of the formalisms are described using the algebraic notion of weak representations of the associated algebras. The book also includes a presentation of fuzzy extensions of qualitative calculi, and a description of the study of complexity in terms of clones of operations.
See More

Table of Contents

Introduction. Qualitative Reasoning xvii

Chapter 1. Allen’s Calculus 1

1.1. Introduction 1

1.2. Allen’s interval relations 6

1.3. Constraint networks 8

1.4. Constraint propagation 17

1.5. Consistency tests 26

Chapter 2. Polynomial Subclasses of Allen’s Algebra 29

2.1. “Show me a tractable relation!” 29

2.2. Subclasses of Allen’s algebra 30

2.3. Maximal tractable subclasses of Allen’s algebra 52

2.4. Using polynomial subclasses 57

2.5. Models of Allen’s language 60

2.6. Historical note 61

Chapter 3. Generalized Intervals 63

3.1. “When they built the bridge .  “ 63

3.2. Entities and relations 65

3.3. The lattice of basic (p, q)-relations 68

3.4. Regions associated with basic (p, q)-relations 69

3.5. Inversion and composition 73

3.6. Subclasses of relations: convex and pre-convex relations 79

3.7. Constraint networks 82

3.8. Tractability of strongly pre-convex relations 83

3.9. Conclusions 84

3.10. Historical note 85

Chapter 4. Binary Qualitative Formalisms 87

4.1. “Night driving” 87

4.2. Directed points in dimension 1 92

4.3. Directed intervals 97

4.4. The OPRA direction calculi 99

4.5. Dipole calculi 100

4.6. The Cardinal direction calculus 101

4.7. The Rectangle calculus 104

4.8. The n-point calculus 106

4.9. The n-block calculus 108

4.10. Cardinal directions between regions 109

4.11. The INDU calculus 123

4.12. The 2n-star calculi 126

4.13. The Cyclic interval calculus 128

4.14. The RCC–8 formalism 131

4.15. A discrete RCC theory 137

Chapter 5. Qualitative Formalisms of Arity Greater than 2 145

5.1. “The sushi bar” 145

5.2. Ternary spatial and temporal formalisms 146

5.3. Alignment relations between regions 155

5.4. Conclusions 158

Chapter 6. Quantitative Formalisms, Hybrids, and Granularity 159

6.1. “Did John meet Fred this morning?”159

6.2. TCSP metric networks 160

6.3. Hybrid networks 164

6.4. Meiri’s formalism 168

6.5. Disjunctive linear relations (DLR) 174

6.6. Generalized temporal networks 175

6.7. Networks with granularity 179

Chapter 7. Fuzzy Reasoning 187

7.1. “Picasso’s Blue period” 187

7.2. Fuzzy relations between classical intervals 188

7.3. Events and fuzzy intervals 195

7.4. Fuzzy spatial reasoning: a fuzzy RCC 208

7.5. Historical note 222

Chapter 8. The Geometrical Approach and Conceptual Spaces 223

8.1. “What color is the chameleon?” 223

8.2. Qualitative semantics 224

8.3. Why introduce topology and geometry? 225

8.4. Conceptual spaces 226

8.5. Polynomial relations of INDU 237

8.6. Historical note 258

Chapter 9. Weak Representations 259

9.1. “Find the hidden similarity” 259

9.2. Weak representations 261

9.3. Classifying the weak representations of An 275

9.4. Extension to the calculi based on linear orders 283

9.5. Weak representations and configurations 290

9.6. Historical note 304

Chapter 10. Models of RCC−8 305

10.1. “Disks in the plane” 305

10.2. Models of a composition table 307

10.3. The RCC theory and its models 312

10.4. Extensional entries of the composition table 319

10.5. The generalized RCC theory 329

10.6. A countable connection algebra 337

10.7. Conclusions 341

Chapter 11. A Categorical Approach of Qualitative Reasoning 343

11.1. “Waiting in line” 343

11.2. A general construction of qualitative formalisms 346

11.3. Examples of partition schemes 349

11.4. Algebras associated with qualitative formalisms 350

11.5. Partition schemes and weak representations 352

11.6. A general definition of qualitative formalisms 353

11.7. Interpretating consistency 355

11.8. The category of weak representations 357

11.9. Conclusions 360

Chapter 12. Complexity of Constraint Languages 363

12.1. “Sudoku puzzles” 363

12.2. Structure of the chapter 365

12.3. Constraint languages 366

12.4. An algebraic approach of complexity 367

12.5. CSPs and morphisms of relational structures 368

12.6. Clones of operations 373

12.7. From local consistency to global consistency 375

12.8. The infinite case 376

12.9. Disjunctive constraints and refinements 382

12.10. Refinements and independence 389

12.11. Historical note 390

Chapter 13. Spatial Reasoning and Modal Logic 391

13.1. “The blind men and the elephant” 391

13.2. Space and modal logics 393

13.3. The modal logic S4 393

13.4. Topological models 396

13.5. Translating the RCC−8 predicates 408

13.6. An alternative modal translation of RCC−8 409

13.7. Generalized frames 410

13.8. Complexity 411

13.9. Complements 412

Chapter 14. Applications and Software Tools 413

14.1. Applications 413

14.2. Software tools 416

Chapter 15. Conclusion and Prospects 423

15.1. Introduction 423

15.2. Combining qualitative formalisms 423

15.3. Spatio-temporal reasoning 426

15.4. Alternatives to qualitative reasoning 430

15.5. To conclude — for good 434

Appendix A. Elements of Topology 435

A.1. Topological spaces 435

A.2. Metric spaces 445

A.3. Connectedness and convexity 447

Appendix B. Elements of Universal Algebra 451

B.1. Abstract algebras 451

B.2. Boolean algebras 452

B.3. Binary relations and relation algebras 454

B.4. Basic elements of the language of categories 457

Appendix C. Disjunctive Linear Relations 463

C.1. DLRs: definitions and satisfiability 463

C.2. Linear programming 464

C.3. Complexity of the satisfiability problem 466

Bibliography 471

Index 501

See More

Buy Both and Save 25%!

+

Qualitative Spatial and Temporal Reasoning (US $219.00)

-and- Smart Grids (US $159.95)

Total List Price: US $378.95
Discounted Price: US $284.21 (Save: US $94.74)

Buy Both
Cannot be combined with any other offers. Learn more.

Related Titles

More in this series

Back to Top