Frank Dylla
Till Mossakowski
Skip Abstract Section
Skip Supplemental Material SectionAbstract
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.
Supplemental Material
Available for Download
zip
dylla.zip (309.8 KB)
Supplemental movie, appendix, image and software files for, A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties
- Marco Aiello and Brammert Ottens. 2007. The Mathematical Morpho-Logical View on Reasoning about Space. In Proc. of the 20th International Joint Conference on Artificial Intelligence (IJCAI’07). Morgan Kaufmann, 205--211.Google Scholar
Digital Library
- Marco Aiello, Ian E. Pratt-Hartmann, and Johan F.A.K. van Benthem (Eds.). 2007. Handbook of Spatial Logics. Springer.Google Scholar
- James F. Allen. 1983. Maintaining knowledge about temporal intervals. Commun. ACM 26, 11 (1983), 832--843. Google ScholarDigital Library
- 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.Google Scholar
- Egidio Astesiano, Michel Bidoit, Hélène Kirchner, Bernd Krieg-Brückner, Peter D. Mosses, Donald Sannella, and Andrzej Tarlecki. 2002. CASL: the Common Algebraic Specification Language. Theor. Comput. Sci. 286, 2 (2002), 153--196. Google ScholarDigital Library
- 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.Google Scholar
- Philippe Balbiani, Jean-François Condotta, and Luis Fariñas del Cerro. 2002. Tractability Results in the Block Algebra. J. Log. Comput. 12, 5 (2002), 885--909. Google ScholarCross Ref
- Philippe Balbiani, Jean-François Condotta, and Gérard Ligozat. 2006. On the consistency problem for the INDU calculus. J. Applied Logic 4, 2 (2006), 119--140. Google ScholarCross Ref
- Philippe Balbiani and Jean-François Condotta. 2002. Spatial reasoning about points in a multidimensional setting. Appl. Intell. 17, 3 (2002), 221--238. Google ScholarDigital Library
- Philippe Balbiani, Jean-François Condotta, and Luis Fariñas del Cerro. 1998. A model for reasoning about bidimensional temporal relations. In Proc. of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR’98). Morgan Kaufmann, 124--130.Google ScholarDigital Library
- Philippe Balbiani, Jean-François Condotta, and Luis Fariñas del Cerro. 1999. A tractable subclass of the block algebra: constraint propagation and preconvex relations. In Proc. of the 9th Portuguese Conference on Artificial Intelligence (EPIA’99) (LNCS), Vol. 1695. Springer, 75--89. Google ScholarCross Ref
- Philippe Balbiani and Aomar Osmani. 2000. A model for reasoning about topologic relations between cyclic intervals. In Proc. of Principles of Knowledge Representation and Reasoning Proceedings of the Seventh International Conference (KR’00). Morgan Kaufmann, 378--385.Google ScholarDigital Library
- Saugata Basu, Richard Pollack, and Marie-Françoise Roy. 2006. Algorithms in Real Algebraic Geometry. Springer.Google Scholar
- 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.Google Scholar
- Brandon Bennett. 1997. Logical Representations for automated reasoning about spatial relationships. Ph.D. Dissertation. The University of Leeds, School of Computer Studies, UK.Google Scholar
- Brandon Bennett, Anthony G. Cohn, Frank Wolter, and Michael Zakharyaschev. 2002. Multi-Dimensional Modal Logic as a Framework for Spatio-Temporal Reasoning. Appl. Intell. 17, 3 (2002), 239--251. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Günter M. Ziegler. 1999. Oriented Matroids. Cambridge University Press. Google ScholarCross Ref
- 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.Google Scholar
- Bert Bredeweg and Peter Struss. 2004. Current Topics in Qualitative Reasoning. AI Mag. 24, 4 (2004), 13--16.Google ScholarDigital Library
- Juan Chen, Anthony G. Cohn, Dayou Liu, Shengsheng Wang, Jihong Ouyang, and Qiangyuan Yu. 2013. A survey of qualitative spatial representations. Knowledge Eng. Review 30, 1 (2013), 106--136. Google ScholarCross Ref
- Eliseo Clementini and Roland Billen. 2006. Modeling and Computing Ternary Projective Relations between Regions. IEEE TKDE 18, 6 (2006), 799--814. Google ScholarDigital Library
- 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.Google Scholar
- Eliseo Clementini, Paolino Di Felice, and Peter van Oosterom. 1993. A Small Set of Formal Topological Relationships Suitable for End-User Interaction. In Proc. of Advances in Spatial Databases, Third International Symposium, (SSD’93) (LNCS), Vol. 692. Springer, 277--295. Google ScholarCross Ref
- Eliseo Clementini, Spiros Skiadopoulos, Roland Billen, and Francesco Tarquini. 2010. A Reasoning System of Ternary Projective Relations. IEEE TKDE 22, 2 (2010), 161--178. Google ScholarDigital Library
- Anthony G. Cohn and Shyamanta M. Hazarika. 2001. Qualitative spatial representation and reasoning: an overview. Fund. Inform. 46 (2001), 1--29.Google ScholarDigital Library
- Anthony G. Cohn, Brandon Bennett, John Gooday, and Nicholas Mark Gotts. 1997. Qualitative Spatial Representation and Reasoning with the Region Connection Calculus. GeoInformatica 1, 3 (1997), 275--316. Google ScholarDigital Library
- Anthony G. Cohn, Sanjiang Li, Weiming Liu, and Jochen Renz. 2014. Reasoning about Topological and Cardinal Direction Relations Between 2-Dimensional Spatial Objects. J. Artif. Intell. Res. (JAIR) 51 (2014), 493--532.Google ScholarDigital Library
- 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.Google Scholar
- Jean-François Condotta. 2000. Tractable Sets of the Generalized Interval Algebra. In Proc. of the 14th European Conference on Artificial Intelligence (ECAI’00). IOS Press, 78--82.Google ScholarDigital Library
- Jean-François Condotta, Gérard Ligozat, and Mahmoud Saade. 2006. A Generic Toolkit for n-ary Qualitative Temporal and Spatial Calculi. In Proc. of the 13th International Symposium on Temporal Representation and Reasoning (TIME’06). IEEE Computer Society, 78--86. Google ScholarDigital Library
- Matteo Cristani. 1999. The Complexity of Reasoning about Spatial Congruence. J. Artif. Intell. Res. (JAIR) 11 (1999), 361--390.Google ScholarDigital Library
- Ernest Davis. 1990. Representations of Commonsense Knowledge. Morgan Kaufmann.Google Scholar
- Rina Dechter. 2003. Constraint processing. Morgan Kaufmann.Google Scholar
- Matthias Delafontaine, Peter Bogaert, Anthony G. Cohn, Frank Witlox, Philippe De Maeyer, and Nico Van de Weghe. 2011. Inferring additional knowledge from QTCN relations. Inf. Sci. 181, 9 (2011), 1573--1590. Google ScholarDigital Library
- 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.Google Scholar
- Ivo Düntsch. 2005. Relation Algebras and their Application in Temporal and Spatial Reasoning. Artif. Intell. Rev. 23, 4 (2005), 315--357. Google ScholarDigital Library
- 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.Google Scholar
- Frank Dylla, Till Mossakowski, Thomas Schneider, and Diedrich Wolter. 2013. Algebraic Properties of Qualitative Spatio-temporal Calculi. In Proc. of the 11th International Conference on Spatial Information Theory (COSIT’13) (LNCS), Vol. 8116. Springer, 516--536. Google ScholarDigital Library
- Frank Dylla and Jan Oliver Wallgrün. 2007. Qualitative Spatial Reasoning with Conceptual Neighborhoods for Agent Control. Journal of Intelligent 8 Robotic Systems 48, 1 (2007), 55--78.Google ScholarDigital Library
- Max J. Egenhofer. 1991. Reasoning about Binary Topological Relations. In Proc. of Advances in Spatial Databases, Second International Symposium (SSD’91) (LNCS 525). 143--160. Google ScholarCross Ref
- Max J. Egenhofer and Jayant Sharma. 1993. Assessing the Consistency of Complete and Incomplete Topological Information. Geographical Systems 1, 1 (1993), 47--68.Google Scholar
- Carola Eschenbach. 2001. Viewing composition tables as axiomatic systems. In Proc. of the 2nd International Conference on Formal Ontology in Information Systems (FOIS’01). ACM Press, 93--104. Google ScholarDigital Library
- Carola Eschenbach and Lars Kulik. 1997. An Axiomatic Approach to the Spatial Relations Underlying Left-Right and in Front of-Behind. In Proc. of the 21st Annual German Conference on Artificial Intelligence (KI’97) (LNCS), Vol. 1303. Springer, 207--218. Google ScholarCross Ref
- Alexander Ferrein, Christian Fritz, and Gerhard Lakemeyer. 2004. On-Line Decision-Theoretic Golog for Unpredictable Domains. In Proc. of the 27th Annual German Conference on Artificial Intelligence (KI’04) (LNCS), Vol. 3238. Springer, 322--336. Google ScholarCross Ref
- Alexander Ferrein and Gerhard Lakemeyer. 2008. Logic-based Robot Control in Highly Dynamic Domains. Robotics and Autonomous Systems 56, 11 (2008), 980--991. Google ScholarDigital Library
- Kenneth D. Forbus, Jeffrey M. Usher, and Vernell Chapman. 2004. Qualitative spatial reasoning about sketch maps. AI Mag. 25, 3 (2004), 61--72.Google ScholarDigital Library
- Andrew U. Frank. 1991. Qualitative Spatial Reasoning with Cardinal Directions. In Proc. of the 7th Austrian Conference on Artificial Intelligence (ÖGAI’91). 157--167. Google ScholarCross Ref
- Andrew U. Frank. 1992. Qualitative spatial reasoning about distances and directions in geographic space. J. Vis. Lang. Comput. 3, 4 (1992), 343--371. Google ScholarCross Ref
- Christian Freksa. 1992a. Temporal Reasoning Based on Semi-Intervals. Artif. Intell. 54, 1 (1992), 199--227. Google ScholarDigital Library
- Christian Freksa. 1992b. Using Orientation Information for Qualitative Spatial Reasoning. In Spatio-Temporal Reasoning (LNCS), Vol. 639. Springer, 162--178. Google ScholarCross Ref
- Christian Freksa and Kai Zimmermann. 1992. On the utilization of spatial structures for cognitively plausible and efficient reasoning. In Proc. of IEEE International Conference on Systems, Man and Cybernetics (ICSMC’92). IEEE, 261--266. Google ScholarCross Ref
- David Gabelaia, Roman Kontchakov, Agi Kurucz, Frank Wolter, and Michael Zakharyaschev. 2005. Combining Spatial and Temporal Logics: Expressiveness vs. Complexity. J. Artif. Intell. Res. (JAIR) 23 (2005), 167--243.Google ScholarDigital Library
- Antony P. Galton. 1994. Lines of Sight. In Proc. of the Seventh Annual Irish Conference on AI and Cognitive Science (AICS’94). 103--113.Google Scholar
- Alfonso Gerevini and Bernhard Nebel. 2002. Qualitative Spatio-Temporal Reasoning with RCC-8 and Allen’s Interval Calculus: Computational Complexity. In Proc. of the 15th European Conference on Artificial Intelligence (ECAI’02). IOS Press, 312--316.Google ScholarDigital Library
- Alfonso Gerevini and Jochen Renz. 2002. Combining topological and size information for spatial reasoning. Artif. Intell. 137, 1--2 (2002), 1--42.Google ScholarDigital Library
- Francisco Jose Glez-Cabrera, José Vicente Álvarez-Bravo, and Fernando Díaz. 2013. QRPC: A new qualitative model for representing motion patterns. Expert Syst. Appl. 40, 11 (2013), 4547--4561. Google ScholarDigital Library
- Björn Gottfried. 2004. Reasoning about intervals in two dimensions. In Proc. of the IEEE International Conference on Systems, Man 8 Cybernetics (ICSMC’04). IEEE, 5324--5332. Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- Volker Haarslev, Kay Hidde, Ralf Möller, and Michael Wessel. 2012. The RacerPro knowledge representation and reasoning system. J. Web Sem. 3, 3 (2012), 267--277.Google ScholarDigital Library
- 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.Google Scholar
- Daniel Hernández. 1994. Qualitative representation of spatial knowledge. LNCS, Vol. 804. Springer, Berlin. Google ScholarCross Ref
- Robin Hirsch and Ian Hodkinson. 2002. Relation algebras by games. Studies in logic and the foundations of mathematics, Vol. 147. Elsevier.Google Scholar
- Helmi Ben Hmida, Frank Boochs, Christophe Cruz, and Christophe Nicolle. 2012. From quantitative spatial operator to qualitative spatial relation using Constructive Solid Geometry, logic rules and optimized 9-IM model: A semantic based approach. In Proc. of IEEE International Conference on Computer Science and Automation Engineering (CSAE’12), Vol. 3. IEEE, 453--458. Google ScholarCross Ref
- Armen Inants and Jérôme Euzenat. 2015. An Algebra of Qualitative Taxonomical Relations for Ontology Alignments. In Proc. of the 14th International Semantic Web (ISWC’15) (LNCS), Vol. 9366. Springer, 253--268. Google ScholarDigital Library
- Amar Isli and Anthony G. Cohn. 2000. A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artif. Intell. 122, 1--2 (2000), 137--187.Google ScholarDigital Library
- Peter Jonsson and Christer Bäckström. 1998. A unifying approach to temporal constraint reasoning. Artif. Intell. 102, 1 (1998), 143--155. Google ScholarDigital Library
- Peter Jonsson and Thomas Drakengren. 1997. A Complete Classification of Tractability in RCC-5. J. Artif. Intell. Res. (JAIR) 6 (1997), 211--221.Google ScholarDigital Library
- 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.Google Scholar
- Donald E. Knuth. 1992. Axioms and Hulls. LNCS, Vol. 606. Springer. Google ScholarCross Ref
- Christian Köhler. 2002. The Occlusion Calculus. In Proc. of Workshop on Cognitive Vision. Zurich, Switzerland.Google Scholar
- Roman Kontchakov, Agi Kurucz, Frank Wolter, and Michael Zakharyaschev. 2007. Spatial Logic + Temporal Logic = ? In Handbook of Spatial Logics. Springer, 497--564. Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- Andrei Krokhin, Peter Jeavons, and Peter Jonsson. 2003. Reasoning about temporal relations: The tractable subalgebras of Allen’s interval algebra. J. ACM 50, 5 (2003), 591--640. Google ScholarDigital Library
- Benjamin Kuipers. 1978. Modeling Spatial Knowledge. Cogn. Sci. 2, 2 (1978), 129--153. Google ScholarCross Ref
- Yohei Kurata. 2010. 9+-intersection calculi for spatial reasoning on the topological relations between heterogeneous objects. In Proc. of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, (ACM-GIS’10). ACM Press, 390--393.Google ScholarDigital Library
- Yohei Kurata and Hui Shi. 2008. Interpreting Motion Expressions in Route Instructions Using Two Projection-Based Spatial Models. In Proc. of the 31st Annual German Conference on AI (KI’08) (LNCS), Vol. 5243. Springer, 258--266. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Stephen C. Levinson. 2003. Space in Language and Cognition: Explorations in Cognitive Diversity. Cambridge University Press, Cambridge. Google ScholarCross Ref
- Sanjiang Li, Weiming Liu, and Shengsheng Wang. 2013. Qualitative constraint satisfaction problems: An extended framework with landmarks. Artif. Intell. 201 (2013), 32--58. Google ScholarDigital Library
- Gérard Ligozat. 1993. Qualitative Triangulation for Spatial Reasoning. In Proc. of the International Conference on Spatial Information Theory (COSIT’93). Springer, 54--68. Google ScholarCross Ref
- Gérard Ligozat. 1998. Reasoning about Cardinal Directions. J. Vis. Lang. Comput. 9, 1 (1998), 23--44. Google ScholarCross Ref
- Gérard Ligozat. 2005. Categorical Methods in Qualitative Reasoning: The Case for Weak Representations. In Proc. of the International Conference on Spatial Information Theory (COSIT’05) (LNCS), Vol. 3693. Springer, 265--282.Google ScholarDigital Library
- Gérard Ligozat. 2011. Qualitative Spatial and Temporal Reasoning. John Wiley 8 Sons.Google Scholar
- Gérard Ligozat and Jochen Renz. 2004. What Is a Qualitative Calculus? A General Framework. In Proc. of the 8th Pacific Rim International Conference on Artificial Intelligence (PRICAI’04) (LNCS), Vol. 3157. Springer, 53--64.Google ScholarDigital Library
- Weiming Liu and Sanjiang Li. 2011. Reasoning about cardinal directions between extended objects: The NP-hardness result. Artif. Intell. 175 (2011), 2155--2169. Google ScholarDigital Library
- 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.Google Scholar
- Weiming Liu, Sanjiang Li, and Jochen Renz. 2009. Combining RCC-8 with Qualitative Direction Calculi: Algorithms and Complexity. In Proc. of the 21st International Joint Conference on Artificial Intelligence (IJCAI’09). AAAI Press, 854--859.Google ScholarDigital Library
- Weiming Liu, Xiaotong Zhang, Sanjiang Li, and Mingsheng Ying. 2010. Reasoning about Cardinal Directions between Extended Objects. Artif. Intell. 174, 12--13 (2010), 951--983.Google ScholarDigital Library
- 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.Google Scholar
- Carsten Lutz and Maja Milićič. 2007. A Tableau Algorithm for Description Logics with Concrete Domains and General TBoxes. J. Autom. Reasoning 38, 1--3 (2007), 227--259.Google ScholarDigital Library
- Alan K. Mackworth. 1977. Consistency in networks of relations. Artif. Intell. 8 (1977), 99--118. Google ScholarDigital Library
- Roger D. Maddux. 2006. Relation algebras. Stud. Logic Found. Math., Vol. 150. Elsevier.Google Scholar
- 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.Google Scholar
- Reinhard Moratz, Dominik Lücke, and Till Mossakowski. 2011. A Condensed Semantics for Qualitative Spatial Reasoning About Oriented Straight Line Segments. Artif. Intell. 175 (2011), 2099--2127. Google ScholarDigital Library
- Reinhard Moratz and Marco Ragni. 2008. Qualitative spatial reasoning about relative point position. J. Vis. Lang. Comput. 19, 1 (2008), 75--98. Google ScholarDigital Library
- Reinhard Moratz, Jochen Renz, and Diedrich Wolter. 2000. Qualitative Spatial Reasoning about Line Segments. In Proc. of the 14th European Conference on Artificial Intelligence (ECAI’00). IOS Press, 234--238.Google ScholarDigital Library
- Reinhard Moratz and Jan Oliver Wallgrün. 2012. Spatial reasoning with augmented points: Extending cardinal directions with local distances. J. Spatial Inf. Sci. 5, 1 (2012), 1--30. Google ScholarCross Ref
- Florian Mossakowski. 2007. Algebraische Eigenschaften qualitativer Constraint-Kalküle. Diploma thesis. Dept. of Comput. Science, University of Bremen. In German.Google Scholar
- 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.Google Scholar
- Till Mossakowski and Reinhard Moratz. 2012. Qualitative Reasoning about Relative Direction of Oriented Points. Artif. Intell. 180--181 (2012), 34--45.Google Scholar
- Till Mossakowski and Reinhard Moratz. 2015. Relations Between Spatial Calculi About Directions and Orientations. J. Artif. Intell. Res. (JAIR) 54 (2015), 277--308.Google ScholarDigital Library
- Isabel Navarrete, Antonio Morales, Guido Sciavicco, and M. Antonia Cárdenas-Viedma. 2013. Spatial reasoning with rectangular cardinal relations -- The convex tractable subalgebra. Ann. Math. Artif. Intell. 67, 1 (2013), 31--70. Google ScholarDigital Library
- Bernhard Nebel and Hans-Jürgen Bürckert. 1995. Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. J. ACM 42, 1 (1995), 43--66. Google ScholarDigital Library
- Bernhard Nebel and Alexander Scivos. 2002. Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning. KI 16, 4 (2002), 14--18.Google Scholar
- Tobias Nipkow, Lawrence C. Paulson, and Markus Wenzel. 2002. Isabelle/HOL, A Proof Assistant for Higher-Order Logic. LNCS, Vol. 2283. Springer.Google Scholar
- Jihong OuYang, Qian Fu, and Dayou Liu. 2007. A Model for Representing Topological Relations Between Simple Concave Regions. In Proc. of the 7th International Conference on Computational Science (ICCS’07) (LNCS), Vol. 4487. Springer, 160--167.Google ScholarDigital Library
- Julio Pacheco, M. Teresa Escrig, and Francisco Toledo. 2001. Representing and Reasoning on Three-Dimensional Qualitative Orientation Point Objects. In Proc. of the 10th Portuguese Conference on Artificial Intelligence, (EPIA’01) (LNCS), Vol. 2258. Springer, 298--305. Google ScholarCross Ref
- Arun K. Pujari, G. Vijaya Kumari, and Abdul Sattar. 1999. INDU: An Interval and Duration Network. In Proc. of the 12th Australian Joint Conference on Artificial Intelligence (AI’99) (LNCS), Vol. 1747. Springer, 291--303.Google ScholarCross Ref
- 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.Google Scholar
- Marco Ragni and Alexander Scivos. 2005. Dependency calculus: Reasoning in a general point relation algebra. In Proc. of the 28th Annual German Conference on AI (KI’05) (LNCS), Vol. 3698. Springer, 49--63.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- Jochen Renz. 2002. Qualitative Spatial Reasoning with Topological Information. LNCS, Vol. 2293. Springer. Google ScholarCross Ref
- 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.Google Scholar
- Jochen Renz and Debasis Mitra. 2004. Qualitative Direction Calculi with Arbitrary Granularity. In Proc. of the 8th Pacific Rim International Conference on Artificial Intelligence (PRICAI’04) (LNCS), Vol. 3157. Springer, 65--74. Google ScholarDigital Library
- Jochen Renz and Bernhard Nebel. 2007. Qualitative spatial reasoning using constraint calculi. See Aiello et al. [2007], 161--215.Google Scholar
- Stuart Russell and Peter Norvig. 2009. Artificial Intelligence: A Modern Approach (3rd ed.). Prentice Hall.Google ScholarDigital Library
- Chaman L. Sabharwal and Jennifer L. Leopold. 2014. Evolution of Region Connection Calculus to VRCC-3D+. New Math. Natural Comput. 10 (2014), 1--39. Issue 20.Google ScholarCross Ref
- Marcus Schaefer, Eric Sedgwick, and Daniel Štefankovič. 2003. Recognizing String Graphs in NP. J. Comput. Syst. Sci. 67, 2 (2003), 365--380. STOC 2002 special issue.Google ScholarDigital Library
- Marcus Schaefer and Daniel Štefankovič. 2004. Decidability of String Graphs. J. Comput. Syst. Sci. 68, 2 (2004), 319--334. STOC 2001 special issue.Google ScholarDigital Library
- Stefan Schiffer, Alexander Ferrein, and Gerhard Lakemeyer. 2012. Reasoning with Qualitative Positional Information for Domestic Domains in the Situation Calculus. J. Intell. and Robotic Systems 66, 1--2 (2012), 273--300.Google ScholarDigital Library
- Steven Schockaert and Sanjiang Li. 2015. Realizing RCC8 networks using convex regions. Artif. Intell. 218 (2015), 74--105. Google ScholarDigital Library
- Steven Schockaert, Philip D. Smart, and Florian A. Twaroch. 2011. Generating approximate region boundaries from heterogeneous spatial information: An evolutionary approach. Inf. Sci. 181, 2 (2011), 257--283. Google ScholarDigital Library
- 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.Google Scholar
- Alexander Scivos and Bernhard Nebel. 2005. The Finest of its Class: The Natural Point-Based Ternary Calculus for Qualitative Spatial Reasoning. In Proc. of Spatial Cognition 2004 (LNCS), Vol. 3343. Springer, 283--303.Google ScholarDigital Library
- Michael Sioutis and Jean-François Condotta. 2014. Tackling Large Qualitative Spatial Network of Scale-Free-Like Structure. In Proceedings of the 8th Hellenic Conference on Artificial Intelligence (SETN’14) (LNCS), Vol. 8445. Springer, 178--191. Google ScholarCross Ref
- Evren Sirin, Bijan Parsia, Bernardo Cuenca Grau, Aditya Kalyanpur, and Yarden Katz. 2007. Pellet: A practical OWL-DL reasoner. J. Web Sem. 5, 2 (2007), 51--53. Google ScholarDigital Library
- Spiros Skiadopoulos and Manolis Koubarakis. 2004. Composing cardinal direction relations. Artif. Intell. 152, 2 (2004), 143--171. Google ScholarDigital Library
- Spiros Skiadopoulos and Manolis Koubarakis. 2005. On the consistency of cardinal direction constraints. Artif. Intell. 163, 1 (2005), 91--135. Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Kazuko Takahashi. 2012. PLCA: A Framework for Qualitative Spatial Reasoning Based on Connection Patterns of Regions. In Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions. IGI Global, Chapter 2, 63--96. Google ScholarCross Ref
- Francesco Tarquini, Giorgio De Felice, Paolo Fogliaroni, and Eliseo Clementini. 2007. A Qualitative Model for Visibility Relations. In Proc. of the 30th Annual German Conference on AI (KI’07) (LNCS), Vol. 4667. Springer, 510--513. Google ScholarDigital Library
- Peter van Beek. 1991. Temporal query processing with indefinite information. Artif. Intell. Med. 3, 6 (1991), 325--339. Google ScholarDigital Library
- Peter van Beek. 1992. Reasoning about qualitative temporal information. Artif. Intell. 58 (1992), 297--326. Google ScholarDigital Library
- Nico Van de Weghe, Bart Kuijpers, Peter Bogaert, and Philippe De Maeyer. 2005. A Qualitative Trajectory Calculus and the Composition of Its Relations. In Proc. of First International Conference on GeoSpatial Semantics (GeoS’05) (LNCS), Vol. 3799. Springer, 60--76. Google ScholarDigital Library
- André van Delden and Till Mossakowski. 2013. Mastering Left and Right -- Different Approaches to a Problem That Is Not Straight Forward. In Proc. of 36th Annual German Conference on AI (KI’13) (LNCS), Vol. 8077. Springer, 248--259.Google ScholarCross Ref
- 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.Google Scholar
- Marc B. Vilain, Henry A. Kautz, and Peter van Beek. 1990. Constraint Propagation Algorithms for Temporal Reasoning: A Revised Report. In Readings in Qualitative Reasoning About Physical Systems. 373--381. Google ScholarCross Ref
- Jan Oliver Wallgrün. 2012. Exploiting Qualitative Spatial Reasoning for Topological Adjustment of Spatial Data. In Proc. of the SIGSPATIAL 2012 International Conference on Advances in Geographic Information Systems (formerly known as GIS), (SIGSPATIAL’12). ACM Press, 229--238. Google ScholarDigital Library
- 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.Google Scholar
- Jan Oliver Wallgrün, Diedrich Wolter, and Kai-Florian Richter. 2010. Qualitative Matching of Spatial Information. In Proc. of the 18th ACM SIGSPATIAL International Symposium on Advances in Geographic Information Systems, (ACM-GIS’10). ACM Press, 300--309. Google ScholarDigital Library
- Christoph Weidenbach, Uwe Brahm, Thomas Hillenbrand, Enno Keen, Christian Theobald, and Dalibor Topić. 2002. SPASS Version 2.0. In Proc. of the 18th International Conference on Automated Deduction (CADE’18) (LNCS), Vol. 2392. Springer, 275--279.Google ScholarCross Ref
- Matthias Westphal. 2015. Qualitative constraint-based reasoning: methods and applications. Ph.D. Dissertation. University of Freiburg, Germany.Google Scholar
- Matthias Westphal, Julien Hué, and Stefan Wölfl. 2014. On the Scope of Qualitative Constraint Calculi. In Proc. of the 37th Annual German Conference on AI (KI’14) (LNCS), Vol. 8736. Springer, 207--218. Google ScholarCross Ref
- 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.Google Scholar
- 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.Google Scholar
- Brian C. Williams and Johan de Kleer. 1991. Qualitative Reasoning About Physical Systems: a Return to Roots. Artif. Intell. 51, 1--3 (1991), 1--9.Google ScholarDigital Library
- 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.Google Scholar
- 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.Google Scholar
- Diedrich Wolter and Jae Hee Lee. 2010. Qualitative reasoning with directional relations. Artif. Intell. 174, 18 (2010), 1498--1507. Google ScholarDigital Library
- 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.Google Scholar
- Diedrich Wolter and Jan Oliver Wallgrün. 2012. Qualitative Spatial Reasoning for Applications: New Challenges and the SparQ Toolbox. In Qualitative Spatio-Temporal Representation and Reasoning: Trends and Future Directions. IGI Global, Chapter 11, 336--362. Google ScholarCross Ref
- Frank Wolter and Michael Zakharyaschev. 2000. Spatial reasoning in RCC--8 with Boolean region terms. In Proc. of the 14th European Conference on Artificial Intelligence (ECAI’00). IOS Press, 244--248.Google ScholarDigital Library
- Michael Worboys. 2013. Using Maptrees to Characterize Topological Change. In Proc. of the 11th International Conference on Spatial Information Theory (COSIT’13) (LNCS), Vol. 8116. Springer, 74--90. Google ScholarDigital Library
- Michael Worboys and M. Duckham. 2004. GIS: A Computing Perspective (2nd ed.). CRC Press, Boca Raton FL.Google ScholarCross Ref
- 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.Google Scholar
Index Terms
- A Survey of Qualitative Spatial and Temporal Calculi: Algebraic and Computational Properties
Recommendations
On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi
Spatial Information TheoryAbstractQualitative calculi play a central role in representing and reasoning about qualitative spatial and temporal knowledge. This paper studies distributive subalgebras of qualitative calculi, which are subalgebras in which (weak) composition ...
On decidability of a logic for order of magnitude qualitative reasoning with bidirectional negligibility
JELIA'12: Proceedings of the 13th European conference on Logics in Artificial IntelligenceQualitative Reasoning (QR) is an area of research within Artificial Intelligence that automates reasoning and problem solving about the physical world. QR research aims to deal with representation and reasoning about continuous aspects of entities ...
Qualitative reasoning under ignorance and information-relevant extraction
This paper is devoted to qualitative reasoning under ignorance. We show how to represent conditional ignorance and informational relevance in the symbolic entropy theory that we have developed in our previous work. This theory allows us to represent ...
Comments