Muutke küpsiste eelistusi

E-raamat: Qualitative Spatial and Temporal Reasoning [Wiley Online]

  • Formaat: 544 pages
  • Sari: ISTE
  • Ilmumisaeg: 25-Nov-2011
  • Kirjastus: ISTE Ltd and John Wiley & Sons Inc
  • ISBN-10: 1118601459
  • ISBN-13: 9781118601457
Teised raamatud teemal:
  • Wiley Online
  • Hind: 231,55 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
Qualitative Spatial and Temporal ReasoningSuurem pilt
  • Formaat: 544 pages
  • Sari: ISTE
  • Ilmumisaeg: 25-Nov-2011
  • Kirjastus: ISTE Ltd and John Wiley & Sons Inc
  • ISBN-10: 1118601459
  • ISBN-13: 9781118601457
Teised raamatud teemal:
Wiley Online e-raamatudRohkem infot Wiley Online kohta
Raamatu kodulehekülg: https://onlinelibrary.wiley.com/doi/book/10.1002/9781118601457
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.
Introduction. Qualitative Reasoning xvii
Chapter 1 Allen's Calculus
1(28)
1.1 Introduction
1(5)
1.1.1 "The mystery of the dark room"
1(4)
1.1.2 Contributions of Allen's formalism
5(1)
1.2 Allen's interval relations
6(2)
1.2.1 Basic relations
6(1)
1.2.2 Disjunctive relations
7(1)
1.3 Constraint networks
8(9)
1.3.1 Definition
8(2)
1.3.2 Expressiveness
10(3)
1.3.3 Consistency
13(4)
1.4 Constraint propagation
17(9)
1.4.1 Operations: inversion and composition
17(1)
1.4.2 Composition table
18(2)
1.4.3 Allen's algebra
20(1)
1.4.4 Algebraic closure
20(2)
1.4.5 Enforcing algebraic closure
22(4)
1.5 Consistency tests
26(3)
1.5.1 The case of atomic networks
26(1)
1.5.2 Arbitrary networks
27(1)
1.5.3 Determining polynomial subsets
28(1)
Chapter 2 Polynomial Subclasses of Allen's Algebra
29(34)
2.1 "Show me a tractable relation!"
29(1)
2.2 Subclasses of Allen's algebra
30(22)
2.2.1 A geometrical representation of Allen's relations
30(3)
2.2.2 Interpretation in terms of granularity
33(2)
2.2.3 Convex and pre-convex relations
35(3)
2.2.4 The lattice of Allen's basic relations
38(6)
2.2.5 Tractability of convex relations
44(1)
2.2.6 Pre-convex relations
45(2)
2.2.7 Polynomiality of pre-convex relations
47(4)
2.2.8 ORD-Horn relations
51(1)
2.3 Maximal tractable subclasses of Allen's algebra
52(5)
2.3.1 An alternative characterization of pre-convex relations
52(2)
2.3.2 The other maximal polynomial subclasses
54(3)
2.4 Using polynomial subclasses
57(3)
2.4.1 Ladkin and Reinefeld's algorithm
57(2)
2.4.2 Empirical study of the consistency problem
59(1)
2.5 Models of Allen's language
60(1)
2.5.1 Representations of Allen's algebra
60(1)
2.5.2 Representations of the time-point algebra
60(1)
2.5.3 ℵ0-categoricity of Allen's algebra
61(1)
2.6 Historical note
61(2)
Chapter 3 Generalized Intervals
63(24)
3.1 "When they built the bridge..."
63(2)
3.1.1 Towards generalized intervals
64(1)
3.2 Entities and relations
65(3)
3.3 The lattice of basic (p, q)-relations
68(1)
3.4 Regions associated with basic (p, q)-relations
69(4)
3.4.1 Associated polytopes
71(2)
3.4.2 M-convexity of the basic relations
73(1)
3.5 Inversion and composition
73(6)
3.5.1 Inversion
73(1)
3.5.2 Composition
74(3)
3.5.3 The algebras of generalized intervals
77(2)
3.6 Subclasses of relations: convex and pre-convex relations
79(3)
3.6.1 (p, q)-relations
79(1)
3.6.2 Convex relations
79(2)
3.6.3 Pre-convex relations
81(1)
3.7 Constraint networks
82(1)
3.8 Tractability of strongly pre-convex relations
83(1)
3.8.1 ORD-Horn relations
84(1)
3.9 Conclusions
84(1)
3.10 Historical note
85(2)
Chapter 4 Binary Qualitative Formalisms
87(58)
4.1 "Night driving"
87(5)
4.1.1 Parameters
89(1)
4.1.2 A panorama of the presented formalisms
89(3)
4.2 Directed points in dimension 1
92(5)
4.2.1 Operations
93(1)
4.2.2 Constraint networks
93(1)
4.2.3 Networks reducible to point networks
94(3)
4.2.4 Arbitrary directed point networks
97(1)
4.3 Directed intervals
97(2)
4.3.1 Operations
98(1)
4.3.2 Constraint networks and complexity
98(1)
4.4 The OPRA direction calculi
99(1)
4.5 Dipole calculi
100(1)
4.6 The Cardinal direction calculus
101(3)
4.6.1 Convex and pre-convex relations
102(1)
4.6.2 Complexity
103(1)
4.7 The Rectangle calculus
104(2)
4.7.1 Convex and pre-convex relations
105(1)
4.7.2 Complexity
106(1)
4.8 The n-point calculus
106(2)
4.8.1 Convexity and pre-convexity
107(1)
4.9 The n-block calculus
108(1)
4.9.1 Convexity and pre-convexity
108(1)
4.10 Cardinal directions between regions
109(14)
4.10.1 Basic relations
109(2)
4.10.2 Operations
111(1)
4.10.3 Consistency of basic networks
112(10)
4.10.4 Applications of the algorithm
122(1)
4.11 The INDU calculus
123(3)
4.11.1 Inversion and composition
123(1)
4.11.2 The lattice of INDU relations
123(1)
4.11.3 Regions associated with INDU relations
124(1)
4.11.4 A non-associative algebra
125(1)
4.12 The 2n-star calculi
126(2)
4.12.1 Inversion and composition
127(1)
4.13 The Cyclic interval calculus
128(3)
4.13.1 Convex and pre-convex relations
130(1)
4.13.2 Complexity of the consistency problem
131(1)
4.14 The RCC---8 formalism
131(6)
4.14.1 Basic relations
132(1)
4.14.2 Allen's relations and RCC---8 relations
133(1)
4.14.3 Operations
134(1)
4.14.4 Maximal polynomial classes of RCC---8
135(2)
4.15 A discrete RCC theory
137(8)
4.15.1 Introduction
137(1)
4.15.2 Entities and relations
137(1)
4.15.3 Mereology
138(1)
4.15.4 Concept of contact and RCC---8 relations
138(1)
4.15.5 Closure, interior and boundary
139(1)
4.15.6 Self-connectedness
140(1)
4.15.7 Paths, distance, and arc-connectedness
141(1)
4.15.8 Distance between regions
142(1)
4.15.9 Conceptual neighborhoods
143(2)
Chapter 5 Qualitative Formalisms of Arity Greater than 2
145(14)
5.1 "The sushi bar"
145(1)
5.2 Ternary spatial and temporal formalisms
146(9)
5.2.1 General concepts
146(1)
5.2.2 The Cyclic point calculus
147(1)
5.2.3 The Double-cross calculus
148(3)
5.2.4 The Flip-flop and LR calculi
151(1)
5.2.5 Practical and natural calculi
152(1)
5.2.6 The consistency problem
153(2)
5.3 Alignment relations between regions
155(3)
5.3.1 Alignment between regions of the plane: the 5-intersection calculus
155(1)
5.3.2 Ternary relations between solids in space
156(1)
5.3.3 Ternary relations on the sphere
157(1)
5.4 Conclusions
158(1)
Chapter 6 Quantitative Formalisms, Hybrids, and Granularity
159(28)
6.1 "Did John meet Fred this morning?"
159(1)
6.1.1 Contents of the chapter
160(1)
6.2 TCSP metric networks
160(4)
6.2.1 Operations
161(1)
6.2.2 The consistency problem
162(2)
6.3 Hybrid networks
164(4)
6.3.1 Kautz and Ladkin's formalism
164(4)
6.4 Meiri's formalism
168(6)
6.4.1 Temporal entities and relations
169(1)
6.4.2 Constraint networks
170(1)
6.4.3 Constraint propagation
170(2)
6.4.4 Tractability issues
172(2)
6.5 Disjunctive linear relations (DLR)
174(1)
6.5.1 A unifying formalism
174(1)
6.5.2 Allen's algebra with constraints on durations
174(1)
6.5.3 Conclusions
175(1)
6.6 Generalized temporal networks
175(4)
6.6.1 Motivations
176(1)
6.6.2 Definition of GTN
176(1)
6.6.3 Expressiveness
177(1)
6.6.4 Constraint propagation
178(1)
6.6.5 Conclusions
179(1)
6.7 Networks with granularity
179(8)
6.7.1 Introduction
179(1)
6.7.2 Granularities and granularity systems
180(2)
6.7.3 Constraint networks
182(2)
6.7.4 Complexity of the consistency problem
184(1)
6.7.5 Propagation algorithms
184(3)
Chapter 7 Fuzzy Reasoning
187(36)
7.1 "Picasso's Blue period"
187(1)
7.2 Fuzzy relations between classical intervals
188(7)
7.2.1 Motivations
188(1)
7.2.2 The fuzzy Point algebra
189(2)
7.2.3 The fuzzy Interval algebra
191(1)
7.2.4 Fuzzy constraint networks
192(1)
7.2.5 Algorithms, tractable subclasses
193(2)
7.2.6 Assessment
195(1)
7.3 Events and fuzzy intervals
195(13)
7.3.1 Fuzzy intervals and fuzzy relations
195(2)
7.3.2 Fuzzy constraints
197(5)
7.3.3 An example of application
202(2)
7.3.4 Complexity
204(2)
7.3.5 Weak logical consequence
206(2)
7.3.6 Assessment
208(1)
7.4 Fuzzy spatial reasoning: a fuzzy RCC
208(14)
7.4.1 Motivations
208(1)
7.4.2 Fuzzy regions
209(1)
7.4.3 Fuzzy RCC relations
209(3)
7.4.4 Fuzzy RCC formulas
212(1)
7.4.5 Semantics
212(1)
7.4.6 Satisfying a finite set of normalized formulas
213(2)
7.4.7 (n; α, β)-models
215(2)
7.4.8 Satisfiability and linear programming
217(1)
7.4.9 Models with a finite number of degrees
218(1)
7.4.10 Links with the egg-yolk calculus
218(4)
7.5 Historical note
222(1)
Chapter 8 The Geometrical Approach and Conceptual Spaces
223(36)
8.1 "What color is the chameleon?"
223(1)
8.2 Qualitative semantics
224(1)
8.3 Why introduce topology and geometry?
225(1)
8.4 Conceptual spaces
226(11)
8.4.1 Higher order properties and relations
228(1)
8.4.2 Notions of convexity
228(2)
8.4.3 Conceptual spaces associated to generalized intervals
230(1)
8.4.4 The conceptual space associated to directed intervals
230(1)
8.4.5 Conceptual space associated with cyclic intervals
231(3)
8.4.6 Conceptual neighborhoods in Allen's relations
234(1)
8.4.7 Dominance spaces and dominance diagrams
235(2)
8.5 Polynomial relations of INDU
237(21)
8.5.1 Consistency
238(8)
8.5.2 Convexity and Horn clauses
246(1)
8.5.3 Pre-convex relations
247(1)
8.5.4 NP-completeness of pre-convex relations
248(1)
8.5.5 Strongly pre-convex relations
248(4)
8.5.6 The subclass G
252(5)
8.5.7 A summary of complexity results for INDU
257(1)
8.6 Historical note
258(1)
Chapter 9 Weak Representations
259(46)
9.1 "Find the hidden similarity"
259(2)
9.2 Weak representations
261(14)
9.2.1 Weak representations of the point algebra
261(1)
9.2.2 Weak representations of Allen's interval algebra
262(9)
9.2.3 Weak representations of the n-interval algebra
271(2)
9.2.4 Constructing the canonical configuration
273(2)
9.3 Classifying the weak representations of An
275(8)
9.3.1 The category of weak representations of An
275(2)
9.3.2 Reinterpretating the canonical construction
277(2)
9.3.3 The canonical construction as adjunction
279(4)
9.4 Extension to the calculi based on linear orders
283(7)
9.4.1 Configurations
284(1)
9.4.2 Description languages and associated algebras
284(1)
9.4.3 Canonical constructions
285(3)
9.4.4 The construction in the case of APointsn
288(2)
9.5 Weak representations and configurations
290(14)
9.5.1 Other qualitative formalisms
290(1)
9.5.2 A non-associative algebra: INDU
291(1)
9.5.3 Interpreting Allen's calculus on the integers
291(1)
9.5.4 Algebraically closed but inconsistent scenarios: the case of cyclic intervals
291(1)
9.5.5 Weak representations of RCC---8
292(10)
9.5.6 From weak representations to configurations
302(1)
9.5.7 Finite topological models
302(1)
9.5.8 Models in Euclidean space
303(1)
9.6 Historical note
304(1)
Chapter 10 Models of RCC---8
305(38)
10.1 "Disks in the plane"
305(2)
10.2 Models of a composition table
307(5)
10.2.1 Complements on weak representations
307(1)
10.2.2 Properties of weak representations
308(3)
10.2.3 Models of the composition table of RCC---8
311(1)
10.3 The RCC theory and its models
312(7)
10.3.1 Composition tables relative to a logical theory
312(1)
10.3.2 The RCC theory
313(2)
10.3.3 Strict models and Boolean connection algebras
315(3)
10.3.4 Consistency of strict models
318(1)
10.4 Extensional entries of the composition table
319(10)
10.4.1 Properties of the triads of a composition table
320(2)
10.4.2 Topological models of RCC
322(1)
10.4.3 Pseudocomplemented lattices
323(3)
10.4.4 Pseudocomplementation and connection
326(1)
10.4.5 Non-strict models
326(2)
10.4.6 Models based on regular closed sets
328(1)
10.5 The generalized RCC theory
329(8)
10.5.1 The mereological component: variations of a set-theoretic theme
330(3)
10.5.2 The topological component
333(2)
10.5.3 The GRCC theory
335(1)
10.5.4 Constructing generalized Boolean connection algebras
335(1)
10.5.5 An application to finite models
336(1)
10.6 A countable connection algebra
337(4)
10.6.1 An interval algebra
337(1)
10.6.2 Defining a connection relation
338(3)
10.6.3 Minimality of the algebra (Bω, Cω)
341(1)
10.7 Conclusions
341(2)
Chapter 11 A Categorical Approach of Qualitative Reasoning
343(20)
11.1 "Waiting in line"
343(3)
11.2 A general construction of qualitative formalisms
346(3)
11.2.1 Partition schemes
346(1)
11.2.2 Description of configurations
347(1)
11.2.3 Weak composition
347(1)
11.2.4 Weak composition and seriality
348(1)
11.3 Examples of partition schemes
349(1)
11.4 Algebras associated with qualitative formalisms
350(2)
11.4.1 Algebras associated with partition schemes
350(1)
11.4.2 Examples
351(1)
11.4.3 Associativity
351(1)
11.5 Partition schemes and weak representations
352(1)
11.5.1 The weak representation associated with a partition scheme
353(1)
11.6 A general definition of qualitative formalisms
353(2)
11.6.1 The pivotal role of weak representations
354(1)
11.6.2 Weak representations as constraints
354(1)
11.6.3 Weak representations as interpretations
355(1)
11.7 Interpretating consistency
355(2)
11.7.1 Inconsistent weak representations
356(1)
11.8 The category of weak representations
357(3)
11.8.1 The algebra of partial orders
357(1)
11.8.2 On the relativity of consistency
358(1)
11.8.3 Semi-strong weak representations
359(1)
11.9 Conclusions
360(3)
Chapter 12 Complexity of Constraint Languages
363(28)
12.1 "Sudoku puzzles"
363(2)
12.2 Structure of the chapter
365(1)
12.3 Constraint languages
366(1)
12.4 An algebraic approach of complexity
367(1)
12.5 CSPs and morphisms of relational structures
368(5)
12.5.1 Basic facts about CSPs
368(1)
12.5.2 CSPs and morphisms of structures
369(1)
12.5.3 Polymorphisms and invariant relations
370(1)
12.5.4 pp-Definable relations and preservation
371(1)
12.5.5 A Galois correspondence
372(1)
12.6 Clones of operations
373(2)
12.6.1 The Boolean case
374(1)
12.7 From local consistency to global consistency
375(1)
12.8 The infinite case
376(6)
12.8.1 Homogeneous and ℵ0-categorical structures
376(1)
12.8.2 Quasi near-unanimity operations
377(1)
12.8.3 Application to the point algebra
378(1)
12.8.4 Application to the RCC---5 calculus
379(1)
12.8.5 Application to pointizable relations of Allen's algebra
380(1)
12.8.6 Applications to the study of complexity
381(1)
12.9 Disjunctive constraints and refinements
382(7)
12.9.1 Disjunctive constraints
382(1)
12.9.2 Guaranteed satisfaction property
383(1)
12.9.3 The k-independence property
384(1)
12.9.4 Refinements
385(4)
12.10 Refinements and independence
389(1)
12.11 Historical note
390(1)
Chapter 13 Spatial Reasoning and Modal Logic
391(22)
13.1 "The blind men and the elephant"
391(2)
13.2 Space and modal logics
393(1)
13.3 The modal logic S4
393(3)
13.3.1 Language and axioms
393(1)
13.3.2 Kripke models
394(2)
13.4 Topological models
396(12)
13.4.1 Topological games
397(1)
13.4.2 The rules of the game
397(1)
13.4.3 End of game
398(1)
13.4.4 Examples of games: example 1
398(1)
13.4.5 Example 2
399(1)
13.4.6 Example 3
400(1)
13.4.7 Games and modal rank of formulas
401(1)
13.4.8 McKinsey and Tarski's theorem
402(2)
13.4.9 Topological bisimulations
404(1)
13.4.10 Expressiveness
405(1)
13.4.11 Relational and topological models
405(1)
13.4.12 From topological models to Kripke models
406(2)
13.4.13 An extended language: S4u
408(1)
13.5 Translating the RCC---8 predicates
408(1)
13.6 An alternative modal translation of RCC---8
409(1)
13.7 Generalized frames
410(1)
13.8 Complexity
411(1)
13.9 Complements
412(1)
13.9.1 Analogs of Kamp operators
412(1)
13.9.2 Space and epistemic logics
412(1)
13.9.3 Other extensions
412(1)
Chapter 14 Applications and Software Tools
413(10)
14.1 Applications
413(3)
14.1.1 Applications of qualitative temporal reasoning
413(1)
14.1.2 Applications of spatial qualitative reasoning
414(1)
14.1.3 Spatio-temporal applications
415(1)
14.2 Software tools
416(7)
14.2.1 The Qualitative Algebra Toolkit (QAT)
416(1)
14.2.2 The SparQ toolbox
417(2)
14.2.3 The GQR system
419(4)
Chapter 15 Conclusion and Prospects
423(12)
15.1 Introduction
423(1)
15.2 Combining qualitative formalisms
423(3)
15.2.1 Tight or loose integration
424(1)
15.2.2 RCC---8 and the Cardinal direction calculus
425(1)
15.2.3 RCC---8, the Rectangle calculus, and the Cardinal direction calculus between regions
425(1)
15.2.4 The lattice of partition schemes
426(1)
15.3 Spatio-temporal reasoning
426(4)
15.3.1 Trajectory calculi
426(2)
15.3.2 Reasoning about space-time
428(2)
15.3.3 Combining space and time
430(1)
15.4 Alternatives to qualitative reasoning
430(4)
15.4.1 Translation in terms of finite CSP
431(2)
15.4.2 Translation into an instance of the SAT problem
433(1)
15.5 To conclude --- for good
434(1)
Appendix A Elements of Topology
435(16)
A.1 Topological spaces
435(10)
A.1.1 Interior, exterior, boundary
436(1)
A.1.2 Properties of the closure operator
436(1)
A.1.3 Properties of the interior operator
437(1)
A.1.4 Closure, interior, complement
437(1)
A.1.5 Defining topological spaces in terms of closed sets
438(1)
A.1.6 Defining topological spaces in terms of operators
438(1)
A.1.7 Pseudocomplement of an open set
439(1)
A.1.8 Pseudosupplement of a closed set
439(1)
A.1.9 Regular sets
440(1)
A.1.10 Axioms of separation
440(1)
A.1.11 Bases of a topology
440(1)
A.1.12 Hierarchy of topologies
441(1)
A.1.13 Preorder topology
441(1)
A.1.14 Constructing topological spaces
442(1)
A.1.15 Continuous maps
443(1)
A.1.16 Homeomorphisms
444(1)
A.2 Metric spaces
445(2)
A.2.1 Minkowski metrics
445(1)
A.2.2 Balls and spheres
445(1)
A.2.3 Bounded sets
446(1)
A.2.4 Topology of a metric space
446(1)
A.2.5 Equivalent metrics
446(1)
A.2.6 Distances between subsets
447(1)
A.2.7 Convergence of a sequence
447(1)
A.3 Connectedness and convexity
447(4)
A.3.1 Connectedness
447(1)
A.3.2 Connected components
448(1)
A.3.3 Convexity
448(3)
Appendix B Elements of Universal Algebra
451(12)
B.1 Abstract algebras
451(1)
B.2 Boolean algebras
452(2)
B.2.1 Boolean algebras of subsets
452(1)
B.2.2 Boolean algebras
453(1)
B.2.3 Stone's representation theorem
453(1)
B.3 Binary relations and relation algebras
454(3)
B.3.1 Binary relations
454(1)
B.3.2 Inversion and composition
455(1)
B.3.3 Proper relation algebras
456(1)
B.3.4 Relation algebras
456(1)
B.3.5 Representations
457(1)
B.4 Basic elements of the language of categories
457(6)
B.4.1 Categories and functors
457(2)
B.4.2 Adjoint functors
459(2)
B.4.3 Galois connections
461(2)
Appendix C Disjunctive Linear Relations
463(8)
C.1 DLRs: definitions and satisfiability
463(1)
C.2 Linear programming
464(2)
C.3 Complexity of the satisfiability problem
466(5)
Bibliography 471(30)
Index 501
Gérard Ligozat is retired professor of computer science, Paris-Sud University.
Püsilink: https://www.kriso.ee/db/9781118601457_pe.html
Märksõnad: