Qualitative spatial and temporal reasoning / Gérard Ligozat

Author:: Ligozat, Gérard
Published:: London, UK : ISTE ; Hoboken, NJ : Wiley, 2012.
Physical Description:: xxxi, 505 pages : illustrations ; 24 cm

Availability

Finding items...

Contents:

Machine generated contents note: ch. 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 -- ch. 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.&aleph;0-categoricity of Allen's algebra -- 2.6.Historical note -- ch. 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 -- ch. 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 -- ch. 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 -- ch. 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 -- ch. 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 -- ch. 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 -- ch. 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 APointsn -- 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 -- ch. 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 -- 10.3.2.The RCC theory -- 10.3.3.Strict models and Boolean connection algebras -- 10.3.4.Consistency of strict models -- 10.4.Extensional entries of the composition table -- 10.4.1.Properties of the triads of a composition table -- 10.4.2.Topological models of RCC -- 10.4.3.Pseudocomplemented lattices -- 10.4.4.Pseudocomplementation and connection -- 10.4.5.Non-strict models -- 10.4.6.Models based on regular closed sets -- 10.5.The generalized RCC theory -- 10.5.1.The mereological component: variations of a set-theoretic theme -- 10.5.2.The topological component -- 10.5.3.The GRCC theory -- 10.5.4.Constructing generalized Boolean connection algebras -- 10.5.5.An application to finite models -- 10.6.A countable connection algebra -- 10.6.1.An interval algebra -- 10.6.2.Defining a connection relation -- 10.6.3.Minimality of the algebra (Bω, Cω) -- 10.7.Conclusions -- ch. 11 A Categorical Approach of Qualitative Reasoning -- and Contents note continued: 11.1."Waiting in line" -- 11.2.A general construction of qualitative formalisms -- 11.2.1.Partition schemes -- 11.2.2.Description of configurations -- 11.2.3.Weak composition -- 11.2.4.Weak composition and seriality -- 11.3.Examples of partition schemes -- 11.4.Algebras associated with qualitative formalisms -- 11.4.1.Algebras associated with partition schemes -- 11.4.2.Examples -- 11.4.3.Associativity -- 11.5.Partition schemes and weak representations -- 11.5.1.The weak representation associated with a partition scheme -- 11.6.A general definition of qualitative formalisms -- 11.6.1.The pivotal role of weak representations -- 11.6.2.Weak representations as constraints -- 11.6.3.Weak representations as interpretations -- 11.7.Interpretating consistency -- 11.7.1.Inconsistent weak representations -- 11.8.The category of weak representations -- 11.8.1.The algebra of partial orders -- 11.8.2.On the relativity of consistency -- 11.8.3.Semi-strong weak representations -- 11.9.Conclusions -- ch. 12 Complexity of Constraint Languages -- 12.1."Sudoku puzzles" -- 12.2.Structure of the chapter -- 12.3.Constraint languages -- 12.4.An algebraic approach of complexity -- 12.5.CSPs and morphisms of relational structures -- 12.5.1.Basic facts about CSPs -- 12.5.2.CSPs and morphisms of structures -- 12.5.3.Polymorphisms and invariant relations -- 12.5.4.pp-Definable relations and preservation -- 12.5.5.A Galois correspondence -- 12.6.Clones of operations -- 12.6.1.The Boolean case -- 12.7.From local consistency to global consistency -- 12.8.The infinite case -- 12.8.1.Homogeneous and &aleph;0-categorical structures -- 12.8.2.Quasi near-unanimity operations -- 12.8.3.Application to the point algebra -- 12.8.4.Application to the RCC---5 calculus -- 12.8.5.Application to pointizable relations of Allen's algebra -- 12.8.6.Applications to the study of complexity -- 12.9.Disjunctive constraints and refinements -- 12.9.1.Disjunctive constraints -- 12.9.2.Guaranteed satisfaction property -- 12.9.3.The k-independence property -- 12.9.4.Refinements -- 12.10.Refinements and independence -- 12.11.Historical note -- ch. 13 Spatial Reasoning and Modal Logic -- 13.1."The blind men and the elephant" -- 13.2.Space and modal logics -- 13.3.The modal logic S4 -- 13.3.1.Language and axioms -- 13.3.2.Kripke models -- 13.4.Topological models -- 13.4.1.Topological games -- 13.4.2.The rules of the game -- 13.4.3.End of game -- 13.4.4.Examples of games: example 1 -- 13.4.5.Example 2 -- 13.4.6.Example 3 -- 13.4.7.Games and modal rank of formulas -- 13.4.8.McKinsey and Tarski's theorem -- 13.4.9.Topological bisimulations -- 13.4.10.Expressiveness -- 13.4.11.Relational and topological models -- 13.4.12.From topological models to Kripke models -- 13.4.13.An extended language: S4u -- 13.5.Translating the RCC---8 predicates -- 13.6.An alternative modal translation of RCC---8 -- 13.7.Generalized frames -- 13.8.Complexity -- 13.9.Complements -- 13.9.1.Analogs of Kamp operators -- 13.9.2.Space and epistemic logics -- 13.9.3.Other extensions -- ch. 14 Applications and Software Tools -- 14.1.Applications -- 14.1.1.Applications of qualitative temporal reasoning -- 14.1.2.Applications of spatial qualitative reasoning -- 14.1.3.Spatio-temporal applications -- 14.2.Software tools -- 14.2.1.The Qualitative Algebra Toolkit (QAT) -- 14.2.2.The SparQ toolbox -- 14.2.3.The GQR system -- ch. 15 Conclusion and Prospects -- 15.1.Introduction -- 15.2.Combining qualitative formalisms -- 15.2.1.Tight or loose integration -- 15.2.2.RCC---8 and the Cardinal direction calculus -- 15.2.3.RCC---8, the Rectangle calculus, and the Cardinal direction calculus between regions -- 15.2.4.The lattice of partition schemes -- 15.3.Spatio-temporal reasoning -- 15.3.1.Trajectory calculi -- 15.3.2.Reasoning about space-time -- 15.3.3.Combining space and time -- 15.4.Alternatives to qualitative reasoning -- 15.4.1.Translation in terms of finite CSP -- 15.4.2.Translation into an instance of the SAT problem -- 15.5.To conclude --- for good -- Appendix A Elements of Topology -- A.1.Topological spaces -- A.1.1.Interior, exterior, boundary -- A.1.2.Properties of the closure operator -- A.1.3.Properties of the interior operator -- A.1.4.Closure, interior, complement -- A.1.5.Defining topological spaces in terms of closed sets -- A.1.6.Defining topological spaces in terms of operators -- A.1.7.Pseudocomplement of an open set -- A.1.8.Pseudosupplement of a closed set -- A.1.9.Regular sets -- A.1.10.Axioms of separation -- A.1.11.Bases of a topology -- A.1.12.Hierarchy of topologies -- A.1.13.Preorder topology -- A.1.14.Constructing topological spaces -- A.1.15.Continuous maps -- A.1.16.Homeomorphisms -- A.2.Metric spaces -- A.2.1.Minkowski metrics -- A.2.2.Balls and spheres -- A.2.3.Bounded sets -- A.2.4.Topology of a metric space -- A.2.5.Equivalent metrics -- A.2.6.Distances between subsets -- A.2.7.Convergence of a sequence -- A.3.Connectedness and convexity -- A.3.1.Connectedness -- A.3.2.Connected components -- A.3.3.Convexity -- Appendix B Elements of Universal Algebra -- B.1.Abstract algebras -- B.2.Boolean algebras -- B.2.1.Boolean algebras of subsets -- B.2.2.Boolean algebras -- B.2.3.Stone's representation theorem -- B.3.Binary relations and relation algebras -- B.3.1.Binary relations -- B.3.2.Inversion and composition -- B.3.3.Proper relation algebras -- B.3.4.Relation algebras -- B.3.5.Representations -- B.4.Basic elements of the language of categories -- B.4.1.Categories and functors -- B.4.2.Adjoint functors -- B.4.3.Galois connections -- Appendix C Disjunctive Linear Relations -- C.1.DLRs: definitions and satisfiability -- C.2.Linear programming -- C.3.Complexity of the satisfiability problem.

Subject(s):

ISBN:

9781848212527
1848212526

Bibliography Note:

Includes bibliographical references and index.

Source of Acquisition:

Purchased with funds from the Paterno Libraries Endowment; 2012

Dedication:

Earth and Minerals Sciences copy selected to honor Alexander Klippel, on the occasion of receiving tenure-promotion; and purchased with funds from the Paterno Libraries Endowment; 2012.

Endowment Note:

Paterno Libraries Endowment

View MARC record | catkey: 8736458