Qualitative Temporal and Spatial Reasoning Revisited

• Abian, A.: Categoricity of denumerable atomless boolean rings. Studia Logica 30(1), 63–67 (1972)

  Article  MATH  MathSciNet  Google Scholar 

• Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)

  MATH  Google Scholar 

• Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM 26(11), 832–843 (1983)

  Article  MATH  Google Scholar 

• Bodirsky, M., Chen, H.: Oligomorphic clones. Algebra Universalis (to appear, 2007)

  Google Scholar 

• Bodirsky, M., Chen, H.: Quantified equality constraints. In: Proceedings of LICS 2007 (to appear, 2007)

  Google Scholar 

• Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 646–659. Springer, Heidelberg (2006) (A journal version is available from the webpage of the first author, 2006)

  Chapter  Google Scholar 

• Bennett, B.: Spatial reasoning with propositional logics. In: International Conference on Knowledge Representation and Reasoning, Morgan Kaufmann, San Francisco (1994)

  Google Scholar 

• 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, pp. 181–213 (2005)

  Google Scholar 

• Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing 34, 720–742 (2005)

  Article  MATH  MathSciNet  Google Scholar 

• Bodirsky, M., Nešetřil, J.: Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation 16(3), 359–373 (2006)

  Article  MATH  MathSciNet  Google Scholar 

• Bodirsky, M.: The core of a countably categorical structure. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 100–110. Springer, Heidelberg (2005)

  Google Scholar 

• Baker, K.A., Pixley, A.F.: Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Math. Z. 143, 165–174 (1974)

  Article  MathSciNet  Google Scholar 

• Chen, H.: The computational complexity of quantified constraint satisfaction. Ph.D. thesis, Cornell University (August 2004)

  Google Scholar 

• Cohen, D., Jeavons, P.: The complexity of constraint languages. Appears in: Handbook of Constraint Programming (2006)

  Google Scholar 

• Duentsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review 23, 315–357 (2005)

  Article  MATH  Google Scholar 

• Dechter, R., van Beek, P.: Local and global relational consistency. TCS 173(1), 283–308 (1997)

  Article  MATH  Google Scholar 

• Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)

  MATH  Google Scholar 

• Evans, D.: Examples of aleph-zero categorical structures. Automorphisms of first-order structures, 33–72 (1994)

  Google Scholar 

• Fisher, M., Gabbay, D., Vila, L.: Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier, Amsterdam (2005)

  MATH  Google Scholar 

• Fraïssé, R.: Theory of Relations. North-Holland, Amsterdam (1986)

  MATH  Google Scholar 

• Freuder, E.C.: A sufficient condition for backtrack-free search. Journal of the ACM 29(1), 24–32 (1982)

  Article  MATH  MathSciNet  Google Scholar 

• 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 28, 57–104 (1999)

  Article  MathSciNet  Google Scholar 

• Hirsch, R.: Relation algebras of intervals. Artificial Intelligence Journal 83, 1–29 (1996)

  Article  MathSciNet  Google Scholar 

• Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)

  MATH  Google Scholar 

• Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency and closure. AI 101(1-2), 251–265 (1998)

  MATH  MathSciNet  Google Scholar 

• Jonsson, P., Drakengren, T.: A complete classification of tractability in RCC-5. J. Artif. Intell. Res. 6, 211–221 (1997)

  MATH  MathSciNet  Google Scholar 

• Koubarakis, M.: From local to global consistency in temporal constraint networks. Theor. Comput. Sci. 173(1), 89–112 (1997)

  Article  MATH  MathSciNet  Google Scholar 

• Koubarakis, M.: Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning. Theoretical Computer Science 266, 311–339 (2001)

  Article  MATH  MathSciNet  Google Scholar 

• Kautz, H., van Beek, P., Vilain, M.: Constraint propagation algorithms: A revised report. Qualitative Reasoning about Physical Systems, 373–381 (1990)

  Google Scholar 

• Ladkin, P.B., Maddux, R.D.: On binary constraint problems. Journal of the Association for Computing Machinery 41(3), 435–469 (1994)

  MATH  MathSciNet  Google Scholar 

• Mackworth, A.K.: Consistency in networks of relations. AI 8, 99–118 (1977)

  MATH  Google Scholar 

• Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: Conference on Principles on Knowledge Representation and Reasoning (KR 1992), pp. 165–176 (1992)

  Google Scholar 

• Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artif. Intell. 108(1-2), 69–123 (1999)

  Article  MATH  MathSciNet  Google Scholar 

• Renz, J., Nebel, B.: Qualitative spatial reasoning using constraint calculi. Handbook of Spatial Logics (to appear, 2007)

  Google Scholar 

Download references