CoChat

A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties

Dylla, Frank, Lee, Jae Hee, Mossakowski, Till, Schneider, Thomas, Delden, André Van, Ven, Jasper Van De, Wolter, Diedrich · 2018 · ACM Computing Surveys
Cited by 53

The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.

Abstract

Qualitative spatial and temporal reasoning (QSTR) is concerned with symbolic knowledge representation, typically over infinite domains. The motivations for employing QSTR techniques include exploiting computational properties that allow efficient reasoning to capture human cognitive concepts in a computational framework. The notion of a qualitative calculus is one of the most prominent QSTR formalisms. This article presents the first overview of all qualitative calculi developed to date and their computational properties, together with generalized definitions of the fundamental concepts and methods that now encompass all existing calculi. Moreover, we provide a classification of calculi according to their algebraic properties.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1145/3038927

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

  • Maintaining knowledge about temporal intervals

    Allen, J. F. (1983) · Communications of the ACM · doi:10.1145/182.358434 · Cited by 7,593 · cited 2×

    “Using Boolean combinations of PC relations, one can simulate Allen interval relations. Nebel and Bürckert [1995] have exploited this relationship to lift a tractable subset to Allen.”
    Background

Research works printed but not linked: 162

  1. 10.5555/1625275.1625307 · doi:10.5555/1625275.1625307
  2. Marco Aiello Ian E. Pratt-Hartmann and Johan F.A.K. van Benthem (Eds.). 2007. Handbook of Spatial Logics. Springer. Marco Aiello Ian E. Pratt-Hartmann and Johan F.A.K. van Benthem (Eds.). 2007. Handbook of Spatial Logics. Springer. · DOI
  3. Nouhad Amaneddine and Jean-François Condotta . 2013 . On the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints . In Proc. of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference (FLAIRS’13) . AAAI Press, 16--21. Nouhad Amaneddine and Jean-François Condotta. 2013. On the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints. In Proc. of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference (FLAIRS’13). AAAI Press, 16--21.
  4. 10.1016/S0304-3975(01)00368-1 · DOI · Paper page
  5. Franz Baader Diego Calvanese Deborah L. McGuinness Daniele Nardi and Peter F. Patel-Schneider (Eds.). 2007. The Description Logic Handbook: Theory Implementation and Applications (2nd ed.). Cambridge University Press. Franz Baader Diego Calvanese Deborah L. McGuinness Daniele Nardi and Peter F. Patel-Schneider (Eds.). 2007. The Description Logic Handbook: Theory Implementation and Applications (2nd ed.). Cambridge University Press. · DOI · Paper page
  6. 10.1093/logcom/12.5.885 · DOI
  7. 10.1016/j.jal.2005.06.002 · doi:10.1016/j.jal.2005.06.002
  8. 10.1023/A:1020079114666 · doi:10.1023/a:1020079114666
  9. 10.5555/3087454.3087469 · doi:10.5555/3087454.3087469
  10. 10.1007/3-540-48159-1_6 · doi:10.1007/3-540-48159-1_6
  11. 10.5555/3087011.3087052 · doi:10.5555/3087011.3087052
  12. Saugata Basu , Richard Pollack , and Marie-Françoise Roy . 2006. Algorithms in Real Algebraic Geometry . Springer . Saugata Basu, Richard Pollack, and Marie-Françoise Roy. 2006. Algorithms in Real Algebraic Geometry. Springer.
  13. Sotiris Batsakis and Euripides G. M . Petrakis . 2011 . SOWL : A framework for handling spatio-temporal information in OWL 2.0. In Proc. of the 5th International Symposium on Rule-Based Reasoning, Programming, and Applications (RuleML’11) (LNCS), Vol. 6826 . Springer , 242--249. Sotiris Batsakis and Euripides G. M. Petrakis. 2011. SOWL: A framework for handling spatio-temporal information in OWL 2.0. In Proc. of the 5th International Symposium on Rule-Based Reasoning, Programming, and Applications (RuleML’11) (LNCS), Vol. 6826. Springer, 242--249.
  14. 10.1023/A:1020083231504 · DOI · Paper page
  15. Mehul Bhatt , Jae Hee Lee, and Carl P. L. Schultz . 2011 . CLP(QS): A Declarative Spatial Reasoning Framework. In Proc. of the 10th International Conference on Spatial Information Theory (COSIT’11) (LNCS), Max J. Egenhofer et al. (Ed.), Vol. 6899 . Springer , 210--230. Mehul Bhatt, Jae Hee Lee, and Carl P. L. Schultz. 2011. CLP(QS): A Declarative Spatial Reasoning Framework. In Proc. of the 10th International Conference on Spatial Information Theory (COSIT’11) (LNCS), Max J. Egenhofer et al. (Ed.), Vol. 6899. Springer, 210--230.
  16. Mehul Bhatt and Seng W . Loke . 2008 . Modelling Dynamic Spatial Systems in the Situation Calculus. Spatial Cognition 8 Computation 8, 1--2 (2008), 86--130. Mehul Bhatt and Seng W. Loke. 2008. Modelling Dynamic Spatial Systems in the Situation Calculus. Spatial Cognition 8 Computation 8, 1--2 (2008), 86--130.
  17. Mehul Bhatt , J. Wenny Rahayu , and Gerald Sterling . 2006 . Qualitative Spatial Reasoning with Topological Relations in the Situation Calculus . In Proc. of the Nineteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS’06) . AAAI Press, 713--718. Mehul Bhatt, J. Wenny Rahayu, and Gerald Sterling. 2006. Qualitative Spatial Reasoning with Topological Relations in the Situation Calculus. In Proc. of the Nineteenth International Florida Artificial Intelligence Research Society Conference (FLAIRS’06). AAAI Press, 713--718.
  18. 10.1017/CBO9780511586507 · doi:10.1017/cbo9780511586507
  19. Manuel Bodirsky and Stefan Wölfl . 2011 . RCC8 Is Polynomial on Networks of Bounded Treewidth . In Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11) . AAAI Press, 756--761. Manuel Bodirsky and Stefan Wölfl. 2011. RCC8 Is Polynomial on Networks of Bounded Treewidth. In Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11). AAAI Press, 756--761.
  20. 10.5555/973340.973343 · doi:10.5555/973340.973343
  21. 10.1017/S0269888913000350 · DOI
  22. 10.1109/TKDE.2006.102 · doi:10.1109/tkde.2006.102
  23. Eliseo Clementini and Anthony G. Cohn . 2014. RCC*-9 and CBM . In Proc. of the 8th International Conference on Geographic Information Science (GIScience’14) (LNCS), Vol. 8728 . Springer, 349--365. Eliseo Clementini and Anthony G. Cohn. 2014. RCC*-9 and CBM. In Proc. of the 8th International Conference on Geographic Information Science (GIScience’14) (LNCS), Vol. 8728. Springer, 349--365.
  24. 10.1007/3-540-56869-7_16 · doi:10.1007/3-540-56869-7_16
  25. 10.1109/TKDE.2009.79 · doi:10.1109/tkde.2009.79
  26. Anthony G. Cohn and Shyamanta M. Hazarika . 2001 . Qualitative spatial representation and reasoning: an overview . Fund. Inform. 46 (2001), 1 -- 29 . Anthony G. Cohn and Shyamanta M. Hazarika. 2001. Qualitative spatial representation and reasoning: an overview. Fund. Inform. 46 (2001), 1--29.
  27. 10.1023/A:1009712514511 · DOI · Paper page
  28. 10.5555/2750423.2750436 · doi:10.5555/2750423.2750436
  29. Anthony G. Cohn and Jochen Renz . 2008 . Qualitative Spatial Representation and Reasoning. Foundations of Artificial Intelligence 3, Handbook of Knowledge Representation and Reasoning ( 2008), 551--596. Anthony G. Cohn and Jochen Renz. 2008. Qualitative Spatial Representation and Reasoning. Foundations of Artificial Intelligence 3, Handbook of Knowledge Representation and Reasoning (2008), 551--596.
  30. 10.5555/3006433.3006451 · doi:10.5555/3006433.3006451
  31. 10.1109/TIME.2006.2 · doi:10.1109/time.2006.2
  32. 10.5555/3013545.3013555 · doi:10.5555/3013545.3013555
  33. Ernest Davis. 1990. Representations of Commonsense Knowledge. Morgan Kaufmann. Ernest Davis. 1990. Representations of Commonsense Knowledge. Morgan Kaufmann.
  34. Rina Dechter. 2003. Constraint processing. Morgan Kaufmann. Rina Dechter. 2003. Constraint processing. Morgan Kaufmann.
  35. 10.1016/j.ins.2010.12.021 · doi:10.1016/j.ins.2010.12.021
  36. Matt Duckham , Sanjiang Li , Weiming Liu , and Zhiguo Long . 2014 . On Redundant Topological Constraints . In Proc. of the 14th International Conference on the Principles of Knowledge Representation and Reasoning (KR’14) . AAAI Press, 618--621. Matt Duckham, Sanjiang Li, Weiming Liu, and Zhiguo Long. 2014. On Redundant Topological Constraints. In Proc. of the 14th International Conference on the Principles of Knowledge Representation and Reasoning (KR’14). AAAI Press, 618--621.
  37. 10.1007/s10462-004-5899-8 · DOI
  38. Frank Dylla and Jae Hee Lee . 2010 . A Combined Calculus on Orientation with Composition Based on Geometric Properties . In Proc. of the 19th European Conference on Artificial Intelligence (ECAI’10) (FAIA), Vol. 215 . IOS Press, 1087--1088. Frank Dylla and Jae Hee Lee. 2010. A Combined Calculus on Orientation with Composition Based on Geometric Properties. In Proc. of the 19th European Conference on Artificial Intelligence (ECAI’10) (FAIA), Vol. 215. IOS Press, 1087--1088.
  39. 10.1007/978-3-319-01790-7_28 · DOI
  40. 10.1007/s10846-006-9099-4 · doi:10.1007/s10846-006-9099-4
  41. 10.1007/3-540-54414-3_36 · DOI · Paper page
  42. Max J. Egenhofer and Jayant Sharma . 1993 . Assessing the Consistency of Complete and Incomplete Topological Information . Geographical Systems 1 , 1 (1993), 47 -- 68 . Max J. Egenhofer and Jayant Sharma. 1993. Assessing the Consistency of Complete and Incomplete Topological Information. Geographical Systems 1, 1 (1993), 47--68.
  43. 10.1145/505168.505178 · doi:10.1145/505168.505178
  44. 10.1007/3540634932_16 · doi:10.1007/3540634932_16
  45. 10.1007/978-3-540-30221-6_25 · DOI
  46. 10.1016/j.robot.2008.08.010 · DOI
  47. 10.5555/1045744.1045752 · doi:10.5555/1045744.1045752
  48. 10.1007/978-3-642-46752-3_17 · doi:10.1007/978-3-642-46752-3_17
  49. 10.1016/1045-926X(92)90007-9 · DOI · Paper page
  50. 10.1016/0004-3702(92)90090-K · DOI · Paper page
  51. 10.1007/3-540-55966-3_10 · DOI · Paper page
  52. 10.1109/ICSMC.1992.271766 · DOI
  53. 10.5555/1622503.1622508 · doi:10.5555/1622503.1622508
  54. Antony P. Galton . 1994 . Lines of Sight . In Proc. of the Seventh Annual Irish Conference on AI and Cognitive Science (AICS’94) . 103--113. Antony P. Galton. 1994. Lines of Sight. In Proc. of the Seventh Annual Irish Conference on AI and Cognitive Science (AICS’94). 103--113.
  55. 10.5555/3000905.3000972 · doi:10.5555/3000905.3000972
  56. 10.1016/S0004-3702(02)00193-5 · DOI
  57. 10.1016/j.eswa.2013.01.058 · doi:10.1016/j.eswa.2013.01.058
  58. 10.1109/ICSMC.2004.1401040 · doi:10.1109/icsmc.2004.1401040
  59. Nicholas Mark Gotts . 1996 . Formalizing Commonsense Topology: The INCH Calculus . In Proc. of the 4th International Symposium on Artificial Intelligence and Mathematics (ISAIM’96) . 72--75. Nicholas Mark Gotts. 1996. Formalizing Commonsense Topology: The INCH Calculus. In Proc. of the 4th International Symposium on Artificial Intelligence and Mathematics (ISAIM’96). 72--75.
  60. Michelangelo Grigni , Dimitris Papadias , and Christos H. Papadimitriou . 1995 . Topological Inference. In Proc. of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI’95) . 901--907. Michelangelo Grigni, Dimitris Papadias, and Christos H. Papadimitriou. 1995. Topological Inference. In Proc. of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI’95). 901--907.
  61. 10.5555/2590200.2590204 · doi:10.5555/2590200.2590204
  62. Torsten Hahmann and Michael Grüninger . 2011 . Multidimensional Mereotopology with Betweenness . In Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11) . AAAI Press, 906--911. Torsten Hahmann and Michael Grüninger. 2011. Multidimensional Mereotopology with Betweenness. In Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11). AAAI Press, 906--911.
  63. 10.1007/BFb0020328 · doi:10.1007/bfb0020328
  64. Robin Hirsch and Ian Hodkinson . 2002. Relation algebras by games. Studies in logic and the foundations of mathematics , Vol. 147 . Elsevier . Robin Hirsch and Ian Hodkinson. 2002. Relation algebras by games. Studies in logic and the foundations of mathematics, Vol. 147. Elsevier.
  65. 10.1109/CSAE.2012.6272992 · DOI
  66. 10.1007/978-3-319-25007-6_15 · DOI · Paper page
  67. 10.1016/S0004-3702(00)00044-8 · DOI
  68. 10.1016/S0004-3702(98)00031-9 · DOI
  69. 10.5555/1622767.1622774 · doi:10.5555/1622767.1622774
  70. Markus Knauff , Gerhard Strube , Corinne Jola , Reinhold Rauh , and Christoph Schlieder . 2004. The Psychological Validity of Qualitative Spatial Reasoning in One Dimension. Spatial Cognition 8 Computation 4, 2 ( 2004 ), 167--188. Markus Knauff, Gerhard Strube, Corinne Jola, Reinhold Rauh, and Christoph Schlieder. 2004. The Psychological Validity of Qualitative Spatial Reasoning in One Dimension. Spatial Cognition 8 Computation 4, 2 (2004), 167--188.
  71. 10.1007/3-540-55611-7 · doi:10.1007/3-540-55611-7
  72. Christian Köhler . 2002 . The Occlusion Calculus . In Proc. of Workshop on Cognitive Vision . Zurich, Switzerland. Christian Köhler. 2002. The Occlusion Calculus. In Proc. of Workshop on Cognitive Vision. Zurich, Switzerland.
  73. 10.1007/978-1-4020-5587-4_9 · DOI
  74. Roman Kontchakov , Ian Pratt-Hartmann , Frank Wolter , and Michael Zakharyaschev . 2010. Spatial logics with connectedness predicates. Log. Meth. Comp. Sci. 6, 3 , Article 7 ( 2010 ), 43 pages. Roman Kontchakov, Ian Pratt-Hartmann, Frank Wolter, and Michael Zakharyaschev. 2010. Spatial logics with connectedness predicates. Log. Meth. Comp. Sci. 6, 3, Article 7 (2010), 43 pages.
  75. Arne Kreutzmann and Diedrich Wolter . 2014 . Qualitative Spatial and Temporal Reasoning with AND/OR Linear Programming . In Proc. of the 21st European Conference on Artificial Intelligence (ECAI’14) (FAIA), Vol. 263 . IOS Press, 495--500. Arne Kreutzmann and Diedrich Wolter. 2014. Qualitative Spatial and Temporal Reasoning with AND/OR Linear Programming. In Proc. of the 21st European Conference on Artificial Intelligence (ECAI’14) (FAIA), Vol. 263. IOS Press, 495--500.
  76. 10.1145/876638.876639 · doi:10.1145/876638.876639
  77. 10.1207/s15516709cog0202_3 · doi:10.1207/s15516709cog0202_3 · Paper page
  78. 10.1145/1869790.1869844 · doi:10.1145/1869790.1869844
  79. 10.1007/978-3-540-85845-4_32 · doi:10.1007/978-3-540-85845-4_32
  80. Jae Hee Lee . 2014 . The Complexity of Reasoning with Relative Directions . In Proc. of the 21st European Conference on Artificial Intelligence (ECAI’14) (FAIA), Vol. 263 . IOS Press, 507--512. Jae Hee Lee. 2014. The Complexity of Reasoning with Relative Directions. In Proc. of the 21st European Conference on Artificial Intelligence (ECAI’14) (FAIA), Vol. 263. IOS Press, 507--512.
  81. Jae Hee Lee , Jochen Renz , and Diedrich Wolter . 2013 . StarVars—Effective Reasoning about Relative Directions . In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13) . AAAI Press, 976--982. Jae Hee Lee, Jochen Renz, and Diedrich Wolter. 2013. StarVars—Effective Reasoning about Relative Directions. In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13). AAAI Press, 976--982.
  82. 10.1017/CBO9780511613609 · DOI · Paper page
  83. 10.1016/j.artint.2013.05.006 · doi:10.1016/j.artint.2013.05.006
  84. 10.1007/3-540-57207-4_5 · DOI
  85. 10.1006/jvlc.1997.9999 · DOI
  86. 10.1007/11556114_17 · doi:10.1007/11556114_17
  87. Gérard Ligozat . 2011. Qualitative Spatial and Temporal Reasoning . John Wiley 8 Sons. Gérard Ligozat. 2011. Qualitative Spatial and Temporal Reasoning. John Wiley 8 Sons.
  88. 10.1007/978-3-540-28633-2_8 · DOI
  89. 10.1016/j.artint.2011.07.005 · doi:10.1016/j.artint.2011.07.005
  90. Weiming Liu and Sanjiang Li . 2012 . Here, There, but Not Everywhere: An Extended Framework for Qualitative Constraint Satisfaction . In Proc. of the 20th European Conference on Artificial Intelligence (ECAI’12) (FAIA), Vol. 242 . IOS Press, 552--557. Weiming Liu and Sanjiang Li. 2012. Here, There, but Not Everywhere: An Extended Framework for Qualitative Constraint Satisfaction. In Proc. of the 20th European Conference on Artificial Intelligence (ECAI’12) (FAIA), Vol. 242. IOS Press, 552--557.
  91. 10.5555/1661445.1661581 · doi:10.5555/1661445.1661581
  92. 10.1016/j.artint.2010.05.006 · DOI
  93. Dominik Lücke and Till Mossakowski . 2010 . A much better polynomial time approximation of consistency in the LR calculus . In Proc. of the Fifth Starting AI Researchers’ Symposium (STAIRS’10) (FAIA), Vol. 222 . IOS Press, 175--185. Dominik Lücke and Till Mossakowski. 2010. A much better polynomial time approximation of consistency in the LR calculus. In Proc. of the Fifth Starting AI Researchers’ Symposium (STAIRS’10) (FAIA), Vol. 222. IOS Press, 175--185.
  94. 10.1007/s10817-006-9049-7 · DOI
  95. 10.1016/0004-3702(77)90007-8 · DOI
  96. Roger D. Maddux . 2006. Relation algebras. Stud. Logic Found. Math ., Vol. 150 . Elsevier . Roger D. Maddux. 2006. Relation algebras. Stud. Logic Found. Math., Vol. 150. Elsevier.
  97. Reinhard Moratz . 2006 . Representing Relative Direction as a Binary Relation of Oriented Points . In Proc. of the 17th European Conference on Artificial Intelligence (ECAI’06) (FAIA), Vol. 141 . IOS Press, 407--411. Reinhard Moratz. 2006. Representing Relative Direction as a Binary Relation of Oriented Points. In Proc. of the 17th European Conference on Artificial Intelligence (ECAI’06) (FAIA), Vol. 141. IOS Press, 407--411.
  98. 10.1016/j.artint.2011.07.004 · doi:10.1016/j.artint.2011.07.004
  99. 10.1016/j.jvlc.2006.11.001 · doi:10.1016/j.jvlc.2006.11.001
  100. 10.5555/3006433.3006483 · doi:10.5555/3006433.3006483
  101. 10.5311/JOSIS.2012.5.84 · doi:10.5311/josis.2012.5.84
  102. Florian Mossakowski . 2007. Algebraische Eigenschaften qualitativer Constraint-Kalküle. Diploma thesis. Dept. of Comput. Science , University of Bremen. In German. Florian Mossakowski. 2007. Algebraische Eigenschaften qualitativer Constraint-Kalküle. Diploma thesis. Dept. of Comput. Science, University of Bremen. In German.
  103. Till Mossakowski , Christian Maeder , and Klaus Lüttich . 2007 . The Heterogeneous Tool Set , Hets. In Proc. of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’07) (LNCS), Vol. 4424 . Springer, 519--522. Till Mossakowski, Christian Maeder, and Klaus Lüttich. 2007. The Heterogeneous Tool Set, Hets. In Proc. of the 13th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’07) (LNCS), Vol. 4424. Springer, 519--522.
  104. Till Mossakowski and Reinhard Moratz . 2012. Qualitative Reasoning about Relative Direction of Oriented Points. Artif. Intell. 180--181 ( 2012 ), 34--45. Till Mossakowski and Reinhard Moratz. 2012. Qualitative Reasoning about Relative Direction of Oriented Points. Artif. Intell. 180--181 (2012), 34--45.
  105. 10.5555/2910557.2910565 · doi:10.5555/2910557.2910565
  106. 10.1007/s10472-012-9327-5 · doi:10.1007/s10472-012-9327-5
  107. 10.1145/200836.200848 · DOI · Paper page
  108. Bernhard Nebel and Alexander Scivos . 2002 . Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning . KI 16 , 4 (2002), 14 -- 18 . Bernhard Nebel and Alexander Scivos. 2002. Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning. KI 16, 4 (2002), 14--18.
  109. Tobias Nipkow , Lawrence C. Paulson , and Markus Wenzel . 2002 . Isabelle/HOL, A Proof Assistant for Higher-Order Logic . LNCS , Vol. 2283 . Springer. Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel. 2002. Isabelle/HOL, A Proof Assistant for Higher-Order Logic. LNCS, Vol. 2283. Springer.
  110. 10.1007/978-3-540-72584-8_21 · doi:10.1007/978-3-540-72584-8_21
  111. 10.1007/3-540-45329-6_30 · doi:10.1007/3-540-45329-6_30
  112. 10.1007/3-540-46695-9_25 · DOI
  113. Arun K. Pujari and Abdul Sattar. 1999. A new framework for reasoning about points, intervals and durations . In Proc. of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI’99) . Morgan Kaufmann, 1259--1267. Arun K. Pujari and Abdul Sattar. 1999. A new framework for reasoning about points, intervals and durations. In Proc. of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI’99). Morgan Kaufmann, 1259--1267.
  114. 10.1007/11551263_6 · doi:10.1007/11551263_6
  115. David A. Randell , Zhan Cui , and Anthony G. Cohn . 1992. A Spatial Logic based on Regions and “Connection ”. In Proc. of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92) . Morgan Kaufmann, 165--176. David A. Randell, Zhan Cui, and Anthony G. Cohn. 1992. A Spatial Logic based on Regions and “Connection”. In Proc. of the 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR’92). Morgan Kaufmann, 165--176.
  116. David A. Randell , Mark Witkowski , and Murray Shanahan . 2001 . From Images to Bodies: Modelling and Exploiting Spatial Occlusion and Motion Parallax . In Proc. of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01) . Morgan Kaufmann, 57--66. David A. Randell, Mark Witkowski, and Murray Shanahan. 2001. From Images to Bodies: Modelling and Exploiting Spatial Occlusion and Motion Parallax. In Proc. of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01). Morgan Kaufmann, 57--66.
  117. Jochen Renz . 1999 . Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis . In Proc. of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI’99) . Morgan Kaufmann, 448--455. Jochen Renz. 1999. Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis. In Proc. of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI’99). Morgan Kaufmann, 448--455.
  118. Jochen Renz . 2001 . A Spatial Odyssey of the Interval Algebra: 1 . Directed Intervals. In Proc. of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01) . Morgan Kaufmann, 51--56. Jochen Renz. 2001. A Spatial Odyssey of the Interval Algebra: 1. Directed Intervals. In Proc. of the 17th International Joint Conference on Artificial Intelligence (IJCAI’01). Morgan Kaufmann, 51--56.
  119. 10.1007/3-540-70736-0 · doi:10.1007/3-540-70736-0
  120. Jochen Renz . 2007 . Qualitative spatial and temporal reasoning: Efficient algorithms for everyone . In Proc. of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07) . Morgan Kaufmann, 526--531. Jochen Renz. 2007. Qualitative spatial and temporal reasoning: Efficient algorithms for everyone. In Proc. of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07). Morgan Kaufmann, 526--531.
  121. 10.1007/978-3-540-28633-2_9 · doi:10.1007/978-3-540-28633-2_9
  122. Jochen Renz and Bernhard Nebel. 2007. Qualitative spatial reasoning using constraint calculi. See Aiello et al. [2007] 161--215. Jochen Renz and Bernhard Nebel. 2007. Qualitative spatial reasoning using constraint calculi. See Aiello et al. [2007] 161--215. · DOI · Paper page
  123. Stuart Russell and Peter Norvig . 2009 . Artificial Intelligence: A Modern Approach ( 3 rd ed.). Prentice Hall . Stuart Russell and Peter Norvig. 2009. Artificial Intelligence: A Modern Approach (3rd ed.). Prentice Hall.
  124. 10.1142/S1793005714500069 · doi:10.1142/s1793005714500069
  125. 10.1016/S0022-0000(03)00045-X · doi:10.1016/s0022-0000(03)00045-x
  126. 10.1016/j.jcss.2003.07.002 · doi:10.1016/j.jcss.2003.07.002
  127. 10.1007/s10846-011-9606-0 · DOI
  128. 10.1016/j.artint.2014.10.002 · doi:10.1016/j.artint.2014.10.002
  129. 10.1016/j.ins.2010.09.021 · DOI
  130. Carl Schultz and Mehul Bhatt . 2012 . Towards a Declarative Spatial Reasoning System . In Proc. of the 20th European Conference on Artificial Intelligence (ECAI’12) (FAIA), Vol. 242 . IOS Press, 925--926. Carl Schultz and Mehul Bhatt. 2012. Towards a Declarative Spatial Reasoning System. In Proc. of the 20th European Conference on Artificial Intelligence (ECAI’12) (FAIA), Vol. 242. IOS Press, 925--926.
  131. 10.1007/978-3-540-32255-9_17 · doi:10.1007/978-3-540-32255-9_17
  132. 10.1007/978-3-319-07064-3_15 · DOI
  133. 10.1016/j.websem.2007.03.004 · DOI · Paper page
  134. 10.1016/S0004-3702(03)00137-1 · DOI · Paper page
  135. 10.1016/j.artint.2004.10.010 · DOI
  136. John G. Stell . 2013 . Granular Description of Qualitative Change . In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13) . AAAI Press, 1111--1117. John G. Stell. 2013. Granular Description of Qualitative Change. In Proc. of the 23rd International Joint Conference on Artificial Intelligence (IJCAI’13). AAAI Press, 1111--1117.
  137. Markus Stocker and Evren Sirin . 2009 . PelletSpatial: A Hybrid RCC-8 and RDF/OWL Reasoning and Query Engine . In Proc. of the 5th International Workshop on OWL: Experiences and Directions (OWLED’09) (CEUR Workshop Proceedings) , Vol. 529 . CEUR-WS.org, 2--31. Markus Stocker and Evren Sirin. 2009. PelletSpatial: A Hybrid RCC-8 and RDF/OWL Reasoning and Query Engine. In Proc. of the 5th International Workshop on OWL: Experiences and Directions (OWLED’09) (CEUR Workshop Proceedings), Vol. 529. CEUR-WS.org, 2--31.
  138. 10.4018/978-1-61692-868-1.ch002 · doi:10.4018/978-1-61692-868-1.ch002
  139. 10.1007/978-3-540-74565-5_52 · DOI
  140. 10.1016/0933-3657(91)90004-U · DOI
  141. 10.1016/0004-3702(92)90011-L · DOI · Paper page
  142. 10.1007/11586180_5 · DOI
  143. 10.1007/978-3-642-40942-4_22 · doi:10.1007/978-3-642-40942-4_22
  144. Marc B. Vilain and Henry A. Kautz. 1986. Constraint propagation algorithms for temporal reasoning . In Proc. of the 5th National Conference on Artificial Intelligence (AAAI’86) . Morgan Kaufmann, 377--382. Marc B. Vilain and Henry A. Kautz. 1986. Constraint propagation algorithms for temporal reasoning. In Proc. of the 5th National Conference on Artificial Intelligence (AAAI’86). Morgan Kaufmann, 377--382.
  145. 10.1016/B978-1-4832-1447-4.50034-1 · DOI · Paper page
  146. 10.1145/2424321.2424351 · doi:10.1145/2424321.2424351
  147. Jan Oliver Wallgrün , Frank Dylla , Alexander Klippel , and Jinlong Yang . 2013 . Understanding Human Spatial Conceptualizations to Improve Applications of Qualitative Spatial Calculi . In Proc. of the 27th International Workshop on Qualitative Reasoning (QR’13) . 131--137. Jan Oliver Wallgrün, Frank Dylla, Alexander Klippel, and Jinlong Yang. 2013. Understanding Human Spatial Conceptualizations to Improve Applications of Qualitative Spatial Calculi. In Proc. of the 27th International Workshop on Qualitative Reasoning (QR’13). 131--137.
  148. 10.1145/1869790.1869833 · DOI
  149. 10.1007/3-540-45620-1_22 · doi:10.1007/3-540-45620-1_22
  150. 10.1007/978-3-319-11206-0_20 · doi:10.1007/978-3-319-11206-0_20
  151. Matthias Westphal and Stefan Wölfl . 2008 . Bipath Consistency Revisited . In Proc. of ECAI 2008 Workshop on Spatial and Temporal Reasoning. IOS Press , Amsterdam, 36--40. Matthias Westphal and Stefan Wölfl. 2008. Bipath Consistency Revisited. In Proc. of ECAI 2008 Workshop on Spatial and Temporal Reasoning. IOS Press, Amsterdam, 36--40.
  152. Matthias Westphal , Stefan Wölfl , and Zeno Gantner . 2009 . GQR: A Fast Solver for Binary Qualitative Constraint Networks . In Proc. of the AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems (TR SS-09-02) . AAAI Press, 51--52. Matthias Westphal, Stefan Wölfl, and Zeno Gantner. 2009. GQR: A Fast Solver for Binary Qualitative Constraint Networks. In Proc. of the AAAI Spring Symposium on Benchmarking of Qualitative Spatial and Temporal Reasoning Systems (TR SS-09-02). AAAI Press, 51--52.
  153. 10.1016/0004-3702(91)90106-T · doi:10.1016/0004-3702(91)90106-t
  154. Stefan Wölfl , Till Mossakowski , and Lutz Schröder . 2007 . Qualitative Constraint Calculi: Heterogeneous Verification of Composition Tables . In Proc. of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS’07) . AAAI Press, 665--670. Stefan Wölfl, Till Mossakowski, and Lutz Schröder. 2007. Qualitative Constraint Calculi: Heterogeneous Verification of Composition Tables. In Proc. of the Twentieth International Florida Artificial Intelligence Research Society Conference (FLAIRS’07). AAAI Press, 665--670.
  155. Stefan Wölfl and Matthias Westphal . 2009 . On Combinations of Binary Qualitative Constraint Calculi . In Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11) . AAAI Press, 967--973. Stefan Wölfl and Matthias Westphal. 2009. On Combinations of Binary Qualitative Constraint Calculi. In Proc. of the 22nd International Joint Conference on Artificial Intelligence (IJCAI’11). AAAI Press, 967--973.
  156. 10.1016/j.artint.2010.09.004 · doi:10.1016/j.artint.2010.09.004
  157. Diedrich Wolter and Jae Hee Lee . 2016 . Connecting Qualitative Spatial and Temporal Representations by Propositional Closure . In Proc. of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16) . 1308--1314. Diedrich Wolter and Jae Hee Lee. 2016. Connecting Qualitative Spatial and Temporal Representations by Propositional Closure. In Proc. of the 25th International Joint Conference on Artificial Intelligence (IJCAI’16). 1308--1314.
  158. 10.4018/978-1-61692-868-1.ch011 · DOI
  159. 10.5555/3006433.3006485 · doi:10.5555/3006433.3006485
  160. 10.1007/978-3-319-01790-7_5 · doi:10.1007/978-3-319-01790-7_5
  161. 10.4324/9780203481554 · DOI · Paper page
  162. Peng Zhang and Jochen Renz . 2014 . Qualitative Spatial Representation and Reasoning in Angry Birds: The Extended Rectangle Algebra . In Proc. of the 14th International Conference on the Principles of Knowledge Representation and Reasoning (KR’14) . AAAI Press. Peng Zhang and Jochen Renz. 2014. Qualitative Spatial Representation and Reasoning in Angry Birds: The Extended Rectangle Algebra. In Proc. of the 14th International Conference on the Principles of Knowledge Representation and Reasoning (KR’14). AAAI Press.

Metadata

Authors
Dylla, F., Lee, J. H., Mossakowski, T., Schneider, T., Delden, A. V., Ven, J. V. D., & Wolter, D.
Venue
ACM Computing Surveys
Published
2017-04-04
Volume
50
Issue
1
Pages
1-39
ISSN
  • 0360-0300
  • 1557-7341
Cited by
53
References
1
Language
en
Funders
  • QShape and LogoSpace
  • DFG-funded SFB/TR 8 “Spatial Cognition,”

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.