{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,23]],"date-time":"2024-09-23T03:45:36Z","timestamp":1727063136804},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540426134"},{"type":"electronic","value":"9783540454243"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45424-1_29","type":"book-chapter","created":{"date-parts":[[2007,8,8]],"date-time":"2007-08-08T02:07:41Z","timestamp":1186538861000},"page":"431-446","source":"Crossref","is-referenced-by-count":16,"title":["Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Scivos","sequence":"first","affiliation":[]},{"given":"Bernhard","family":"Nebel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,11,13]]},"reference":[{"issue":"11","key":"29_CR1","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J. F. Allen","year":"1983","unstructured":"J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 26(11):832\u2013843, Nov. 1983.","journal-title":"Communications of the ACM"},{"key":"29_CR2","series-title":"Lect Notes Comput Sci","first-page":"143","volume-title":"Proceedings of the Second Symposium on Large Spatial Databases, SSD\u201991","author":"M. J. Egenhofer","year":"1991","unstructured":"M. J. Egenhofer. Reasoning about binary topological relations. In O. G\u00fcnther and H.-J. Schek, editors, Proceedings of the Second Symposium on Large Spatial Databases, SSD\u201991, volume 525 of Lecture Notes in Computer Science, pages 143\u2013160. Springer-Verlag, Berlin, Heidelberg, New York, 1991."},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"B. Faltings. Qualitative spatial reaoning using algebraic topology. In A. U. Frank and W. Kuhn, editors, Spatial Information Theory: a Basis for GIS, pages 17\u201330. Springer-Verlag, 1995.","DOI":"10.1007\/3-540-60392-1_2"},{"key":"29_CR4","doi-asserted-by":"crossref","unstructured":"A. Frank. Qualitative spatial reasoning with cardinal directions. In Proceedings of the Seventh Austrian Conference on Artificial Intelligence, Berlin, Heidelberg, New York, 1991. Springer-Verlag.","DOI":"10.1007\/978-3-642-46752-3_17"},{"key":"29_CR5","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1007\/3-540-55966-3_10","volume-title":"Theories and Methods of Spatio-Temporal Reasoning in Geographic Space","author":"C. Freksa","year":"1992","unstructured":"C. Freksa. Using orientation information for qualitative spatial reasoning. In A. U. Frank, I. Campari, and U. Formentini, editors, Theories and Methods of Spatio-Temporal Reasoning in Geographic Space, pages 162\u2013178. Springer-Verlag, Berlin, Heidelberg, New York, 1992."},{"key":"29_CR6","unstructured":"C. Freksa and K. Zimmermann. On the utilization of spatial structures for cognitively plausible and efficient reasoning. In Proc. of the IEEE International Conference on Systems, Man, and Cybernetics, pages 261\u2013266, Chicago, IL, 1992. IEEE."},{"key":"29_CR7","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability\u2014A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979."},{"issue":"5","key":"29_CR8","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1145\/174147.169675","volume":"40","author":"M. C. Golumbic","year":"1993","unstructured":"M. C. Golumbic and R. Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. Journal of the Association for Computing Machinery, 40(5):1128\u20131133, Nov. 1993.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"29_CR9","unstructured":"M. Grigni, D. Papadias, and C. Papadimitriou. Topological inference. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI-95), pages 901\u2013906, Montreal, Canada, Aug. 1995. Morgan Kaufmann."},{"issue":"1-2","key":"29_CR10","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/S0004-3702(00)00044-8","volume":"122","author":"A. Isli","year":"2000","unstructured":"A. Isli and A. G. Cohn. A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artificial Intelligence, 122(1-2):137\u2013187, 2000.","journal-title":"Artificial Intelligence"},{"key":"29_CR11","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1016\/S0364-0213(78)80003-2","volume":"2","author":"B. J. Kuipers","year":"1978","unstructured":"B. J. Kuipers. Modelling spatial knowledge. Cognitive Science, 2:129\u2013153, 1978.","journal-title":"Cognitive Science"},{"issue":"3","key":"29_CR12","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","volume":"41","author":"P. B. Ladkin","year":"1994","unstructured":"P. B. Ladkin and R. Maddux. On binary constraint problems. Journal of the Association for Computing Machinery, 41(3):435\u2013469, May 1994.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"29_CR13","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-57322-4_4","volume-title":"Artificial Intelligence and Symbolic Mathematical Computing","author":"P. B. Ladkin","year":"1993","unstructured":"P. B. Ladkin and A. Reinefeld. A symbolic approach to interval constraint problems. In J. Calmet and J. A. Campbell, editors, Artificial Intelligence and Symbolic Mathematical Computing, volume 737 of Lecture Notes in Computer Science, pages 65\u201384. Springer-Verlag, Berlin, Heidelberg, New York, 1993."},{"key":"29_CR14","unstructured":"L. Latecki and R. R\u00f6hrig. Orientation and qualitative angle for spatial reasoning. In Proceedings of the 13th International Joint Conference on Artificial Intelligence (IJCAI-93), pages 1544\u20131549, Chambery, France, Aug. 1993. Morgan Kaufmann."},{"issue":"1","key":"29_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1006\/jvlc.1997.9999","volume":"9","author":"G. Ligozat","year":"1998","unstructured":"G. Ligozat. Reasoning about cardinal directions. Journal of Visual Languages and Computing, 9(1):23\u201344, 1998.","journal-title":"Journal of Visual Languages and Computing"},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A. K. Mackworth","year":"1977","unstructured":"A. K. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99\u2013118, 1977.","journal-title":"Artificial Intelligence"},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"U. Montanari","year":"1974","unstructured":"U. Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Science, 7:95\u2013132, 1974.","journal-title":"Information Science"},{"key":"29_CR18","unstructured":"B. Nebel. Computational properties of qualitative spatial reasoning: First results. In I. Wachsmuth, C.-R. Rollinger, and W. Brauer, editors, KI-95: Advances in Artificial Intelligence, pages 233\u2013244, Bielefeld, Germany, 1995. Springer-Verlag."},{"key":"29_CR19","unstructured":"B. Nebel. Solving hard qualitative temporal reasoning problems: Evaluating the efficiency of using the ORD-Horn class. In Proceedings of the 12th European Conference on Artificial Intelligence (ECAI-96), pages 38\u201342, Budapest, Hungary, Aug. 1996. Wiley."},{"issue":"1","key":"29_CR20","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","volume":"42","author":"B. Nebel","year":"1995","unstructured":"B. Nebel and H.-J. B\u00fcrckert. Reasoning about temporal relations: A maximal tractable subclass of Allen\u2019s interval algebra. Journal of the Association for Computing Machinery, 42(1):43\u201366, Jan. 1995.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"29_CR21","unstructured":"D. A. Randell, Z. Cui, and A. G. Cohn. A spatial logic based on regions and connection. In B. Nebel, W. Swartout, and C. Rich, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference (KR-92), pages 165\u2013176, Cambridge, MA, Oct. 1992. Morgan Kaufmann."},{"issue":"3","key":"29_CR22","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/S0747-7171(10)80003-3","volume":"13","author":"J. Renegar","year":"1992","unstructured":"J. Renegar. On the computational complexity and geometry of the first order theory of the reals. Part I\u2013III. Journal of Symbolic Computation, 13(3):255\u2013300, 301\u2013328, 329\u2013352, 1992.","journal-title":"Journal of Symbolic Computation"},{"key":"29_CR23","unstructured":"J. Renz and B. Nebel. Efficient methods for qualitative spatial reasoning. In Proceedings of the 13th European Conference on Artificial Intelligence (ECAI-98), pages 562\u2013566, Brighton, UK, Aug. 1998. Wiley."},{"issue":"1-2","key":"29_CR24","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0004-3702(99)00002-8","volume":"108","author":"J. Renz","year":"1999","unstructured":"J. Renz and B. Nebel. On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus. Artificial Intelligence, 108(1-2):69\u2013123, 1999.","journal-title":"Artificial Intelligence"},{"key":"29_CR25","unstructured":"A. Scivos. Einf\u00fchrung in eine Theorie der tern\u00e4ren RST-Kalk\u00fcle f\u00fcr qualitatives r\u00e4umliches Schlie\u03b2en. Diplomarbeit, Albert-Ludwigs-Universit\u00e4t Freiburg, Mathematische Fakult\u00e4t, 2000."},{"key":"29_CR26","unstructured":"M. B. Vilain and H. A. Kautz. Constraint propagation algorithms for temporal reasoning. In Proceedings of the 5th National Conference of the American Association for Artificial Intelligence (AAAI-86), pages 377\u2013382, Philadelphia, PA, Aug. 1986."},{"key":"29_CR27","first-page":"373","volume-title":"Readings in Qualitative Reasoning about Physical Systems","author":"M. B. Vilain","year":"1989","unstructured":"M. B. Vilain, H. A. Kautz, and P. G. van Beek. Constraint propagation algorithms for temporal reasoning: A revised report. In D. S. Weld and J. de Kleer, editors, Readings in Qualitative Reasoning about Physical Systems, pages 373\u2013381. Morgan Kaufmann, San Francisco, CA, 1989."},{"issue":"4","key":"29_CR28","first-page":"21","volume":"7","author":"K. Zimmermann","year":"1993","unstructured":"K. Zimmermann and C. Freksa. Qualitatives r\u00e4umliches Schlie\u03b2en mit Wissen \u00fcber Richtungen, Entfernungen und Pfade. K\u00fcnstliche Intelligenz, 7(4):21\u201328, 1993.","journal-title":"K\u00fcnstliche Intelligenz"}],"container-title":["Lecture Notes in Computer Science","Spatial Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45424-1_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T16:38:12Z","timestamp":1556728692000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45424-1_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540426134","9783540454243"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-45424-1_29","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}