{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:44:57Z","timestamp":1725489897485},"publisher-location":"Berlin, Heidelberg","reference-count":34,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540749141"},{"type":"electronic","value":"9783540749158"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-74915-8_17","type":"book-chapter","created":{"date-parts":[[2007,8,24]],"date-time":"2007-08-24T01:13:35Z","timestamp":1187918015000},"page":"194-207","source":"Crossref","is-referenced-by-count":7,"title":["Qualitative Temporal and Spatial Reasoning Revisited"],"prefix":"10.1007","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[]},{"given":"Hubie","family":"Chen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"17_CR1","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/BF02120830","volume":"30","author":"A. Abian","year":"1972","unstructured":"Abian, A.: Categoricity of denumerable atomless boolean rings. Studia Logica\u00a030(1), 63\u201367 (1972)","journal-title":"Studia Logica"},{"key":"17_CR2","volume-title":"Foundations of Databases","author":"S. Abiteboul","year":"1995","unstructured":"Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)"},{"issue":"11","key":"17_CR3","doi-asserted-by":"publisher","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J.F. Allen","year":"1983","unstructured":"Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM\u00a026(11), 832\u2013843 (1983)","journal-title":"Communications of the ACM"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Chen, H.: Oligomorphic clones. Algebra Universalis (to appear, 2007)","DOI":"10.1007\/s00012-007-2026-0"},{"key":"17_CR5","doi-asserted-by":"crossref","unstructured":"Bodirsky, M., Chen, H.: Quantified equality constraints. In: Proceedings of LICS 2007 (to appear, 2007)","DOI":"10.1109\/LICS.2007.38"},{"key":"17_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"646","DOI":"10.1007\/11672142_53","volume-title":"STACS 2006","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., Dalmau, V.: Datalog and constraint satisfaction with infinite templates. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 646\u2013659. Springer, Heidelberg (2006) (A journal version is available from the webpage of the first author, 2006)"},{"key":"17_CR7","volume-title":"International Conference on Knowledge Representation and Reasoning","author":"B. Bennett","year":"1994","unstructured":"Bennett, B.: Spatial reasoning with propositional logics. In: International Conference on Knowledge Representation and Reasoning, Morgan Kaufmann, San Francisco (1994)"},{"key":"17_CR8","unstructured":"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\u2013213 (2005)"},{"key":"17_CR9","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Krokhin, A., Jeavons, P.G.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing\u00a034, 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"17_CR10","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1093\/logcom\/exi083","volume":"16","author":"M. Bodirsky","year":"2006","unstructured":"Bodirsky, M., Ne\u0161et\u0159il, J.: Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation\u00a016(3), 359\u2013373 (2006)","journal-title":"Journal of Logic and Computation"},{"key":"17_CR11","series-title":"Lecture Notes in Computer Science","first-page":"100","volume-title":"STACS 2005","author":"M. Bodirsky","year":"2005","unstructured":"Bodirsky, M.: The core of a countably categorical structure. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 100\u2013110. Springer, Heidelberg (2005)"},{"key":"17_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF01187059","volume":"143","author":"K.A. Baker","year":"1974","unstructured":"Baker, K.A., Pixley, A.F.: Polynomial interpolation and the Chinese remainder theorem for algebraic systems. Math. Z.\u00a0143, 165\u2013174 (1974)","journal-title":"Math. Z."},{"key":"17_CR13","unstructured":"Chen, H.: The computational complexity of quantified constraint satisfaction. Ph.D. thesis, Cornell University (August 2004)"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Cohen, D., Jeavons, P.: The complexity of constraint languages. Appears in: Handbook of Constraint Programming (2006)","DOI":"10.1016\/S1574-6526(06)80012-X"},{"key":"17_CR15","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/s10462-004-5899-8","volume":"23","author":"I. Duentsch","year":"2005","unstructured":"Duentsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artificial Intelligence Review\u00a023, 315\u2013357 (2005)","journal-title":"Artificial Intelligence Review"},{"issue":"1","key":"17_CR16","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0304-3975(97)86737-0","volume":"173","author":"R. Dechter","year":"1997","unstructured":"Dechter, R., van Beek, P.: Local and global relational consistency. TCS\u00a0173(1), 283\u2013308 (1997)","journal-title":"TCS"},{"key":"17_CR17","volume-title":"Finite Model Theory","author":"H.-D. Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory, 2nd edn. Springer, Heidelberg (1999)","edition":"2"},{"key":"17_CR18","unstructured":"Evans, D.: Examples of aleph-zero categorical structures. Automorphisms of first-order structures, 33\u201372 (1994)"},{"key":"17_CR19","volume-title":"Handbook of Temporal Reasoning in Artificial Intelligence","author":"M. Fisher","year":"2005","unstructured":"Fisher, M., Gabbay, D., Vila, L.: Handbook of Temporal Reasoning in Artificial Intelligence. Elsevier, Amsterdam (2005)"},{"key":"17_CR20","volume-title":"Theory of Relations","author":"R. Fra\u00efss\u00e9","year":"1986","unstructured":"Fra\u00efss\u00e9, R.: Theory of Relations. North-Holland, Amsterdam (1986)"},{"issue":"1","key":"17_CR21","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1145\/322290.322292","volume":"29","author":"E.C. Freuder","year":"1982","unstructured":"Freuder, E.C.: A sufficient condition for backtrack-free search. Journal of the ACM\u00a029(1), 24\u201332 (1982)","journal-title":"Journal of the ACM"},{"key":"17_CR22","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1137\/S0097539794266766","volume":"28","author":"T. Feder","year":"1999","unstructured":"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\u00a028, 57\u2013104 (1999)","journal-title":"SIAM Journal on Computing"},{"key":"17_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0004-3702(95)00042-9","volume":"83","author":"R. Hirsch","year":"1996","unstructured":"Hirsch, R.: Relation algebras of intervals. Artificial Intelligence Journal\u00a083, 1\u201329 (1996)","journal-title":"Artificial Intelligence Journal"},{"key":"17_CR24","volume-title":"A shorter model theory","author":"W. Hodges","year":"1997","unstructured":"Hodges, W.: A shorter model theory. Cambridge University Press, Cambridge (1997)"},{"issue":"1-2","key":"17_CR25","first-page":"251","volume":"101","author":"P. Jeavons","year":"1998","unstructured":"Jeavons, P., Cohen, D., Cooper, M.: Constraints, consistency and closure. AI\u00a0101(1-2), 251\u2013265 (1998)","journal-title":"AI"},{"key":"17_CR26","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1613\/jair.379","volume":"6","author":"P. Jonsson","year":"1997","unstructured":"Jonsson, P., Drakengren, T.: A complete classification of tractability in RCC-5. J. Artif. Intell. Res.\u00a06, 211\u2013221 (1997)","journal-title":"J. Artif. Intell. Res."},{"issue":"1","key":"17_CR27","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0304-3975(96)00192-2","volume":"173","author":"M. Koubarakis","year":"1997","unstructured":"Koubarakis, M.: From local to global consistency in temporal constraint networks. Theor. Comput. Sci.\u00a0173(1), 89\u2013112 (1997)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR28","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/S0304-3975(00)00177-8","volume":"266","author":"M. Koubarakis","year":"2001","unstructured":"Koubarakis, M.: Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning. Theoretical Computer Science\u00a0266, 311\u2013339 (2001)","journal-title":"Theoretical Computer Science"},{"key":"17_CR29","unstructured":"Kautz, H., van Beek, P., Vilain, M.: Constraint propagation algorithms: A revised report. Qualitative Reasoning about Physical Systems, 373\u2013381 (1990)"},{"issue":"3","key":"17_CR30","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","volume":"41","author":"P.B. Ladkin","year":"1994","unstructured":"Ladkin, P.B., Maddux, R.D.: On binary constraint problems. Journal of the Association for Computing Machinery\u00a041(3), 435\u2013469 (1994)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"17_CR31","first-page":"99","volume":"8","author":"A.K. Mackworth","year":"1977","unstructured":"Mackworth, A.K.: Consistency in networks of relations. AI\u00a08, 99\u2013118 (1977)","journal-title":"AI"},{"key":"17_CR32","unstructured":"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\u2013176 (1992)"},{"issue":"1-2","key":"17_CR33","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0004-3702(99)00002-8","volume":"108","author":"J. Renz","year":"1999","unstructured":"Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the region connection calculus. Artif. Intell.\u00a0108(1-2), 69\u2013123 (1999)","journal-title":"Artif. Intell."},{"key":"17_CR34","doi-asserted-by":"crossref","unstructured":"Renz, J., Nebel, B.: Qualitative spatial reasoning using constraint calculi. Handbook of Spatial Logics (to appear, 2007)","DOI":"10.1007\/978-1-4020-5587-4_4"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74915-8_17.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:45:46Z","timestamp":1619505946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74915-8_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540749141","9783540749158"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74915-8_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}