Abstract
In [8] Bennett, Isli and Cohn put out the following challenge to researchers working with theories based on composition tables (CT): give a general characterization of theories and relational constraint languages for which a complete proof procedure can be specified by a CT. For theories based on CTs, they make the distinction between a weak, consistency-based interpretation of the CT, and a stronger extensional definition. In this paper, we take up a limited aspect of the challenge, namely, we characterize a subclass of formalisms for which the weak interpretation can be related in a canonical way to a structure based on a total ordering, while the strong interpretations have the property of aleph-zero categoricity (all countable models are isomorphic).
Our approach is based on algebraic, rather than logical, methods. It can be summarized by two keywords: relation algebra and weak representation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allen, J. F. Maintaining Knowledge about Temporal Intervals. Comm. of the ACM, 26:11, 832–843, 1983.
F.D. Anger, D. Mitra, and R.V. Rodriguez. Temporal Constraint Networks in Nonlinear Time. In Proc. of the ECAI-98 Workshop on Spatial and Temporal Reasoning (W22), pages 33–39, Brighton, UK.
P. Balbiani and A. Osmani. A model for reasoning about topologic relations between cyclic intervals. In Proc. of KR-2000, Breckenridge, Colorado, 2000.
Ph. Balbiani, J.-F. Condotta, and L. Fariñas del Cerro. A model for reasoning about bidimensional temporal relations. In Proc. of KR-98, pages 124–130, 1998.
Ph. Balbiani, J.-F. Condotta, and L. Fariñas del Cerro. A new tractable subclass of the rectangle algebra. In Proc. of IJCAI-99, pages 442–447, 1999.
Ph. Balbiani, J.-F. Condotta, and L. Fariñas del Cerro. Spatial reasoning about points in a multidimensional setting. In Proc. of the IJCAI-99 Workshop on Spatial and Temporal Reasoning, pages 105–113, 1999.
Ph. Balbiani, J.-F. Condotta, and L. Fariñas del Cerro. A tractable subclass of the block algebra: constraint propagation and preconvex relations. In Proc. of the Ninth Portuguese Conference on Artificial Intelligence (EPIA’99), pages 75–89, 1999.
B. Bennett, A. Isli, and A. Cohn. When does a Composition Table Provide a Complete and Tractable Proof Procedure for a Relational Constraint Language? In Proc. of the IJCAI-97 Workshop on Spatial and Temporal Reasoning, pages 75–81, Nagoya, Japan, 1997.
M. Broxvall and P. Jonsson. Disjunctive Temporal Reasoning in Partially Ordered Models of Time. In Proc. of AAAI-2000, Austin, Texas, 2000.
M.J. Egenhofer and R. Franzosa. Point-set topological spatial relations. Int. J. Geo. Info. Sys. 5(2), 161–174, 1991.
B. Jónsson and A. Tarski. Boolean algebras with operators, part II. American J. of Mathematics, 74:127–162, 1952.
P. Ladkin. Models of Axioms for Time Intervals. In Proc. of AAAI-87, 1987.
G. Ligozat. Generalized Intervals: A Guided Tour. In Proc. of the ECAI-98 Workshop on Spatial and Temporal Reasoning (W22), pages 11–18, Brighton, UK, 1998.
G. Ligozat. Weak Representations of Interval Algebras. In Proc. of AAAI-90, pages 715–720, 1990.
G. Ligozat. On generalized interval calculi. In Proc. of AAAI-91, pages 234–240, 1991.
G. Ligozat. Reasoning about Cardinal Directions. J. of Visual Languages and Computing, 9:23–44, 1998.
G. Ligozat. Simple Models for Simple Calculi. In C. Freksa and D.M. Mark, editors, Proc. of COSIT’99, number 1661 in LNCS, pages 173–188. Springer Verlag, 1999.
C.H. Papadimitriou, D. Suciu and V. Vianu. Topological Queries in Spatial Databases. In Proc. ACM SIGACT-SIGMOD-SIGART Symp. on Principles of Database Systems, pages 81–92, 1996.
D. Randell, Z. Cui, and T. Cohn. A spatial logic based on regions and connection. In B. Neumann, editor, Proc. of KR-92, pages 165–176, San Mateo, CA, 1992. Morgan Kaufmann.
J. Renz. A canonical model of the region connection calculus. In Proc. of KR’98, Trento, Italy, 1998.
L. Segoufin and V. Vianu. Querying Spatial Databases via Topological Invariants. In Proc. ACM Symp. on Principles of Database Systems, 1998.
A. Tarski. On the calculus of relations. Journal of Symbolic Logic, 6:73–89, 1941.
P.K. Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
D. van Dalen. Logic and Structure. Springer, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ligozat, G. (2001). When Tables Tell It All: Qualitative Spatial and Temporal Reasoning Based on Linear Orderings. In: Montello, D.R. (eds) Spatial Information Theory. COSIT 2001. Lecture Notes in Computer Science, vol 2205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45424-1_5
Download citation
DOI: https://doi.org/10.1007/3-540-45424-1_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42613-4
Online ISBN: 978-3-540-45424-3
eBook Packages: Springer Book Archive