Skip Navigation



Journal of Logic and Computation Advance Access published online on June 26, 2009
Journal of Logic and Computation, doi:10.1093/logcom/exp025
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Bodirsky, M.
Right arrow Articles by Chen, H.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2009. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original Papers

Qualitative Temporal and Spatial Reasoning Revisited1

Manuel Bodirsky

Laboratoire d’informatique (LIX, CNRS UMR 6171), École Polytechnique, Paris-Palaiseau, France.
E-mail: bodirsky{at}lix.polytechnique.fr

Hubie Chen

Departament de Tecnologies de la Informació i les Comunicacions, Universitat Pompeu Fabra, Barcelona, Spain.
E-mail: hubie.chen{at}upf.edu

Received 14 November 2007.

Establishing local consistency is one of the main algorithmic techniques in temporal and spatial reasoning. Acentral question for the various proposed temporal and spatial constraint languages is whether local consistency implies global consistency. Showing that a constraint language {Gamma} has this ‘local-to-global’ property implies polynomial-time tractability of the constraint language, and has further pleasant algorithmic consequences. In the present article, we study the ‘local-to-global’ property by making use of a recently established connection of this property with universal algebra. Roughly speaking, the connection shows that this property is equivalent to the presence of a so-called quasi near-unanimity (QNU) polymorphism of the constraint language. We obtain new algorithmic results and give very concise proofs of previously known theorems. Our results concern well-known and heavily studied formalisms such as the point algebra, Allen's interval algebra and the spatial reasoning language RCC-5.

Keywords: Temporal reasoning; spatial reasoning; constraint satisfaction; computational complexity; consistency; nearunanimity operations

1 An extended abstract of this article appeared in the 16th EACSL Annual Conference on Computer Science and Logic (CSL 2007).



References

  1. Abian A. Categoricity of denumerable atomless Boolean rings. Studia Logica (1972) 30:63–67.[CrossRef]
  2. Abiteboul S, Hull R, Vianu V. Foundations of Databases (1995) Addison Wesley.
  3. Allen JF. Maintaining knowledge about temporal intervals. Communications of the ACM (1983) 26:832–843.[CrossRef][Web of Science]
  4. Baker KA, Pixley AF. Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Mathematische Zeitschrift (1974) 143:165–174.[CrossRef][Web of Science]
  5. Balbiani P, Condotta J-F, del Cerro LF. A new tractable subclass of the rectangle algebra. (1999) Morgan Kaufmann. 442–447. In Proceedings of the International Joint Conference on Artificial Intelligence.
  6. Bennett B. Spatial reasoning with propositional logics. (1994) Morgan Kaufmann. In Proceedings of the International Conference on Knowledge Representation and Reasoning.
  7. Bodirsky M. Constraint satisfaction problems with infinite templates. Vollmer H, ed. (2008) Springer. In Complexity of Constraints (a collection of survey articles), Vol. of Lecture Notes in Computer Science. (forthcomming).
  8. Bodirsky M, Chen H. Oligomorphic clones. Algebra Universalis (2007) 57:109–125.[CrossRef][Web of Science]
  9. Bodirsky M, Chen H. Quantified equality constraints. In: Proceedings of Logic in Computer Science’07 (2007) IEEE Computer Society. 203–212.
  10. Bodirsky M, Dalmau V. Datalog and constraint satisfaction with infinite templates. In: Proceedings of Symposium on Theoretical Aspects of Computer Science’06 (2006) 646–659.
  11. Bodirsky M, Dalmau V. Datalog and constraint satisfaction with infinite templates. An extended abstract appeared. In: Proceedings of Symposium on Theoretical Aspects of Computer Science’06. The full version is available online at arXiv:0809.2386v2 [cs.LO] (2008).
  12. Bodirsky M, Nesetril J. Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation (2006) 16:359–373.[Abstract/Free Full Text]
  13. Bulatov A, Krokhin A, Jeavons PG. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing (2005) 34:720–742.[CrossRef][Web of Science]
  14. Bulatov A, Jeavons P, Krokhin A. The complexity of constraint satisfaction: an algebraic approach (a survey paper). In: Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics, Chemistry (2005) 207:181–213.[CrossRef]
  15. Chen H. The computational complexity of quantified constraint satisfaction (2004) Cornell University. PhD Thesis.
  16. Cohen D, Jeavons P. The complexity of constraint languages. In: Handbook of Constraint Programming—Rossi F, van Beek P, Walsh T, eds. (2006) Elsevier. ch. 8.
  17. Dechter R. From local to global consistency. Artificial Intelligence (1992) 55:87–108.[CrossRef][Web of Science]
  18. Duentsch I. Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review (2005) 23:315–357.[CrossRef][Web of Science]
  19. Ebbinghaus H-D, Flum J. Finite Model Theory (1999) 2nd edn. Springer.
  20. Evans D. Examples of N0-categorical structures. In: Automorphisms of First-order Structures—Kaye R, Macpherson HD, eds. (1994) Oxford University Press. 33–72.
  21. Feder T, Vardi M. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing (1999) 28:57–104.[CrossRef][Web of Science]
  22. Fisher M, Gabbay D, Vila L, eds. Handbook of Temporal Reasoning in Artificial Intelligence (2005) Elsevier.
  23. Fraïssé R. Theory of Relations (1986) North-Holland: Elsevier Science Ltd.
  24. Freuder EC. A sufficient condition for backtrack-free search. Journal of the ACM (1982) 29:24–32.[CrossRef][Web of Science]
  25. Guesgen H. Spatial reasoning based on Allen's temporal logic. In: Report ICSI TR 89-049 (1989) International Computer Science Institute.
  26. Hell P, Nesetril J. The core of a graph. Discrete Mathematics (1992) 109:117–126.[CrossRef][Web of Science]
  27. Hirsch R. Relation algebras of intervals. Artificial Intelligence Journal (1996) 83:1–29.[CrossRef]
  28. Hodges W. A Shorter Model Theory (1997) Cambridge University Press.
  29. Jeavons P, Cohen D, Cooper M. Constraints, consistency and closure. Artificial Intelligence (1998) 101:251–265.[CrossRef][Web of Science]
  30. Jonsson P, Drakengren T. A complete classification of tractability in RCC-5. Journal of Artificial Intellegence Research (1997) 6:211–221.
  31. Kolaitis PG, Vardi MY. Conjunctive-query containment and constraint satisfaction. In. Proceedings of Principles of Database Systems’98 (1998) 205–213.
  32. Koubarakis M. From local to global consistency in temporal constraint networks. Theoritical Computer Science (1997) 173:89–112.[CrossRef]
  33. Koubarakis M. Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning. Theoretical Computer Science (2001) 266:311–339.[CrossRef][Web of Science]
  34. Ladkin PB, Maddux RD. On binary constraint problems. Journal of the Association for Computing Machinery (1994) 41:435–469.
  35. Mackworth AK. Consistency in networks of relations. Artificial Intelligence (1977) 8:99–118.[CrossRef][Web of Science]
  36. Randell DA, Cui Z, Cohn AG. A spatial logic based on regions and connection. (1992) 165–176. In Proceedings of the Conference on Principles on Knowledge Representation and Reasoning (KR’92).
  37. Renz J, Nebel B. On the complexity of qualitative spatial reasoning: a maximal tractable fragment of the region connection calculus. Artificial Intelligence (1999) 108:69–123.[CrossRef][Web of Science]
  38. Renz J, Nebel B. Qualitative spatial reasoning using constraint calculi. In. In: Handbook of Spatial Logics—Aiello M, Pratt-Hartmann I, van Benthem J, eds. (2007) Berlin: Springer Verlag. 161–215.
  39. van Beek P, Cohen R. Exact and approximate reasoning about temporal relations. Computational Intelligence (1990) 6:132–144.[CrossRef]
  40. Vilain HKM, van Beek P. Constraint propagation algorithms for temporal reasoning: a revised report. In. In: Reading in Qualitative Reasoning about Physical Systems (1989) Morgan Kaufmann. 373–381.

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Bodirsky, M.
Right arrow Articles by Chen, H.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?