{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T02:52:34Z","timestamp":1712458354703},"reference-count":51,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[2004,7,1]],"date-time":"2004-07-01T00:00:00Z","timestamp":1088640000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3339,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2004,7]]},"DOI":"10.1016\/j.artint.2004.02.003","type":"journal-article","created":{"date-parts":[[2004,3,29]],"date-time":"2004-03-29T00:36:12Z","timestamp":1080520572000},"page":"177-196","source":"Crossref","is-referenced-by-count":7,"title":["The complexity of constraint satisfaction problems for small relation algebras"],"prefix":"10.1016","volume":"156","author":[{"given":"M.","family":"Cristani","sequence":"first","affiliation":[]},{"given":"R.","family":"Hirsch","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.artint.2004.02.003_BIB001","doi-asserted-by":"crossref","first-page":"421","DOI":"10.1007\/BF00370681","article-title":"The origin of relation algebras in the development and axiomatization of the calculus of relations","volume":"3\/4","author":"Maddux","year":"1991","journal-title":"Studia Logica"},{"key":"10.1016\/j.artint.2004.02.003_BIB002","series-title":"Algebraic Logic","first-page":"1","article-title":"Nineteenth century roots of algebraic logic and universal algebra","volume":"vol. 54","author":"Anellis","year":"1991"},{"key":"10.1016\/j.artint.2004.02.003_BIB003","series-title":"Proc. IJCAI-83, Karsruhe, Germany","first-page":"711","article-title":"Planning using a temporal world model","author":"Allen","year":"1983"},{"key":"10.1016\/j.artint.2004.02.003_BIB004","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/3-540-57322-4_4","article-title":"A symbolic approach to interval constraint problems","volume":"737","author":"Ladkin","year":"1993","journal-title":"Artificial Intelligence Symbol. Math. Comput."},{"key":"10.1016\/j.artint.2004.02.003_BIB005","series-title":"Proc. IJCAI-81, Vancouver, BC","first-page":"221","article-title":"An interval-based representation of temporal knowledge","author":"Allen","year":"1981"},{"issue":"11","key":"10.1016\/j.artint.2004.02.003_BIB006","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","article-title":"Maintaining knowledge about temporal intervals","volume":"26","author":"Allen","year":"1983","journal-title":"Comm. ACM"},{"issue":"2","key":"10.1016\/j.artint.2004.02.003_BIB007","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1016\/0004-3702(84)90008-0","article-title":"Towards a general theory of action and time","volume":"23","author":"Allen","year":"1984","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.artint.2004.02.003_BIB008","series-title":"Proc. IJCAI-85, Los Angeles, CA","first-page":"528","article-title":"A commonsense theory of time","author":"Allen","year":"1985"},{"key":"10.1016\/j.artint.2004.02.003_BIB009","series-title":"Contributions to Artificial Intelligence, vol. 1","article-title":"A model of na\u0131\u0308ve temporal reasoning","author":"Allen","year":"1983"},{"key":"10.1016\/j.artint.2004.02.003_BIB010","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/0004-3702(91)90006-6","article-title":"Temporal constraint networks","volume":"49","author":"Dechter","year":"1991","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.artint.2004.02.003_BIB011","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","article-title":"On binary constraint problems","volume":"41","author":"Ladkin","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/j.artint.2004.02.003_BIB012","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90061-0","article-title":"Temporal database management","volume":"32","author":"Dean","year":"1987","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.artint.2004.02.003_BIB013","series-title":"Workshop Notes of the Spatial and Temporal Reasoning at ECAI 98, Brighton, UK","article-title":"Temporal constraint networks in nonlinear time","author":"Anger","year":"1998"},{"key":"10.1016\/j.artint.2004.02.003_BIB014","series-title":"Proc. Florida Artificial Intelligence Research Society Conference, Orlando, FL","article-title":"Satisfiability in nonlinear time: Algorithms and complexity","author":"Anger","year":"1999"},{"issue":"2\u20133","key":"10.1016\/j.artint.2004.02.003_BIB015","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1023\/A:1009729828056","article-title":"Determining consistency of topological relations","volume":"3","author":"Bennett","year":"1998","journal-title":"Constraints"},{"key":"10.1016\/j.artint.2004.02.003_BIB016","series-title":"Advances in Spatial Databases-Second Symposium SSD'91, New York","first-page":"143","article-title":"Reasoning about binary topological relations","volume":"vol. 525","author":"Egenhofer","year":"1991"},{"issue":"4","key":"10.1016\/j.artint.2004.02.003_BIB017","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/1045-926X(92)90007-9","article-title":"Qualitative spatial reasoning about distances and directions","volume":"3","author":"Frank","year":"1992","journal-title":"J. Visual Languages Comput."},{"issue":"1","key":"10.1016\/j.artint.2004.02.003_BIB018","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0004-3702(85)90041-4","article-title":"The complexity of some polynomial network consistency algorithms for constraint satisfaction problems","volume":"25","author":"Mackworth","year":"1985","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.artint.2004.02.003_BIB019","series-title":"Proc. AAAI-86, Philadelphia, PA","first-page":"377","article-title":"Constraint propagation algorithms for temporal reasoning","author":"Vilain","year":"1986"},{"key":"10.1016\/j.artint.2004.02.003_BIB020","series-title":"Proc. AAAI-87, Seattle, WA","first-page":"256","article-title":"The satisfiability of temporal constraint networks","author":"Vald\u00e9s-Per\u00e9z","year":"1987"},{"key":"10.1016\/j.artint.2004.02.003_BIB021","series-title":"Readings in Qualitative Reasoning about Physical Systems","first-page":"373","article-title":"Constraint propagation algorithms for temporal reasoning\u2014A revised report","author":"Vilain","year":"1989"},{"key":"10.1016\/j.artint.2004.02.003_BIB022","series-title":"Foundations of Constraint Satisfaction","author":"Tsang","year":"1993"},{"key":"10.1016\/j.artint.2004.02.003_BIB023","series-title":"Proc. ISMIS","article-title":"parcplan: A planning architecture with parallel actions, resources and constraints","author":"Lever","year":"1994"},{"key":"10.1016\/j.artint.2004.02.003_BIB024","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0004-3702(99)00089-2","article-title":"Tractable approximations for temporal constraint handling","volume":"116","author":"Hirsch","year":"2000","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.artint.2004.02.003_BIB025","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/S0304-3975(99)00156-5","article-title":"A relation algebraic approach to the region connection calculus","volume":"255","author":"D\u00fcntsch","year":"2001","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/j.artint.2004.02.003_BIB026","first-page":"71","article-title":"Algebras of approximating regions","volume":"46","author":"D\u00fcntsch","year":"2001","journal-title":"Fund. Inform."},{"key":"10.1016\/j.artint.2004.02.003_BIB027","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1023\/A:1013892110192","article-title":"A necessary relation algebra for mereotopology","volume":"69","author":"D\u00fcntsch","year":"2001","journal-title":"Studia Logica"},{"key":"10.1016\/j.artint.2004.02.003_BIB028","series-title":"KR'02: Principles of Knowledge Representation and Reasoning","first-page":"265","article-title":"Many-sorted preference relations","author":"Cristani","year":"2002"},{"key":"10.1016\/j.artint.2004.02.003_BIB029","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1007\/BF02280664","article-title":"Small integral relation algebras generated by a partial order","volume":"23","author":"D\u00fcntsch","year":"1991","journal-title":"Periodica Mathematica Hungarica"},{"issue":"4","key":"10.1016\/j.artint.2004.02.003_BIB030","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1305\/ndjfl\/1040408612","article-title":"Representations for small relation algebras","volume":"35","author":"Andr\u00e9ka","year":"1994","journal-title":"Notre Dame J. Formal Logic"},{"issue":"3","key":"10.1016\/j.artint.2004.02.003_BIB031","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1093\/logcom\/7.3.309","article-title":"Expressive power and complexity in algebraic logic","volume":"7","author":"Hirsch","year":"1997","journal-title":"J. Logic Comput."},{"issue":"4","key":"10.1016\/j.artint.2004.02.003_BIB032","first-page":"547","article-title":"A relation algebra with undecidable network satisfaction problem","volume":"7","author":"Hirsch","year":"1999","journal-title":"Bull. Interest Group Pure Appl. Logics"},{"key":"10.1016\/j.artint.2004.02.003_BIB033","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0743-1066(93)90016-A","article-title":"A temporal extension of prolog","volume":"15","author":"Hrycej","year":"1993","journal-title":"J. Logic Programming"},{"key":"10.1016\/j.artint.2004.02.003_BIB034","doi-asserted-by":"crossref","first-page":"73","DOI":"10.2307\/2268577","article-title":"On the calculus of relations","volume":"6","author":"Tarski","year":"1941","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/j.artint.2004.02.003_BIB035","doi-asserted-by":"crossref","first-page":"127","DOI":"10.2307\/2372074","article-title":"Boolean algebras with operators II","volume":"74","author":"J\u00f3nsson","year":"1952","journal-title":"Amer. J. Math."},{"key":"10.1016\/j.artint.2004.02.003_BIB036","series-title":"Relation Algebras by Games","author":"Hirsch","year":"2002"},{"key":"10.1016\/j.artint.2004.02.003_BIB037","series-title":"Algebraic Logic","first-page":"361","article-title":"Introductory course on relation algebras, finite-dimensional cylindric algebras, and their interconnections","volume":"vol. 54","author":"Maddux","year":"1991"},{"key":"10.1016\/j.artint.2004.02.003_BIB038","unstructured":"R. Maddux, Relation algebras, in preparation"},{"key":"10.1016\/j.artint.2004.02.003_BIB039","series-title":"Complexity of Computer Computations","first-page":"85","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972"},{"key":"10.1016\/j.artint.2004.02.003_BIB040","series-title":"Computers and Intractability\u2014A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"issue":"3","key":"10.1016\/j.artint.2004.02.003_BIB041","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1145\/176584.176585","article-title":"On binary constraint problems","volume":"41","author":"Ladkin","year":"1994","journal-title":"J. ACM"},{"key":"10.1016\/j.artint.2004.02.003_BIB042","series-title":"Encyclopedia of Mathematics and its Applications, second reprint","article-title":"Model theory","author":"Hodges","year":"1995"},{"key":"10.1016\/j.artint.2004.02.003_BIB043","article-title":"Oligomorphic Permutation Groups","volume":"vol. 152","author":"Cameron","year":"1990"},{"issue":"1","key":"10.1016\/j.artint.2004.02.003_BIB044","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1145\/200836.200848","article-title":"Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra","volume":"42","author":"Nebel","year":"1995","journal-title":"J. ACM"},{"key":"10.1016\/j.artint.2004.02.003_BIB045","series-title":"Proc. AAAI-96, Portland, OR","first-page":"389","article-title":"Maximal tractable subclasses of Allen's interval algebra: Preliminary report","author":"Drakengren","year":"1996"},{"issue":"1\u20132","key":"10.1016\/j.artint.2004.02.003_BIB046","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1016\/S0004-3702(97)00021-0","article-title":"Twenty-one large tractable subclasses of Allen's algebra","volume":"93","author":"Drakengren","year":"1997","journal-title":"Artificial Intelligence"},{"issue":"1\u20132","key":"10.1016\/j.artint.2004.02.003_BIB047","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/S0004-3702(99)00007-7","article-title":"Computational complexity of relating time points with intervals","volume":"109","author":"Jonsson","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.artint.2004.02.003_BIB048","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1613\/jair.379","article-title":"A complete classification of tractability in the spatial theory RCC-5","volume":"6","author":"Jonsson","year":"1997","journal-title":"J. Artificial Intelligence Res."},{"issue":"1\u20132","key":"10.1016\/j.artint.2004.02.003_BIB049","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0004-3702(99)00002-8","article-title":"On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus","volume":"108","author":"Renz","year":"1999","journal-title":"Artificial Intelligence"},{"key":"10.1016\/j.artint.2004.02.003_BIB050","series-title":"Proc. IJCAI-99, Stockholm, Sweden","article-title":"Maximal tractable fragments of the Region Connection Calculus: A complete analysis","author":"Renz","year":"1999"},{"key":"10.1016\/j.artint.2004.02.003_BIB051","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1613\/jair.641","article-title":"The complexity of reasoning about spatial congruence","volume":"11","author":"Cristani","year":"1999","journal-title":"J. Artificial Intelligence Res."}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370204000268?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370204000268?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,31]],"date-time":"2020-03-31T20:23:39Z","timestamp":1585686219000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370204000268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,7]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,7]]}},"alternative-id":["S0004370204000268"],"URL":"https:\/\/doi.org\/10.1016\/j.artint.2004.02.003","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[2004,7]]}}}