{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,3]],"date-time":"2025-11-03T09:07:19Z","timestamp":1762160839537,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540667490"},{"type":"electronic","value":"9783540467670"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-46767-x_1","type":"book-chapter","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T21:12:51Z","timestamp":1269897171000},"page":"1-18","source":"Crossref","is-referenced-by-count":8,"title":["Fixed-Parameter Complexity in AI and Nonmonotonic Reasoning"],"prefix":"10.1007","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"given":"Francesco","family":"Scarcello","sequence":"additional","affiliation":[]},{"given":"Martha","family":"Sideri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2000,3,3]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/B978-0-934613-40-8.50006-3","volume-title":"Foundations of Deductive Databases and Logic Programming","author":"K. Apt","year":"1988","unstructured":"K. Apt, H. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 89\u2013148. Morgan Kaufman, Washington DC, 1988."},{"key":"1_CR2","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1016\/0004-3702(88)90023-9","volume":"35","author":"W. Bibel","year":"1988","unstructured":"W. Bibel. Constraint Satisfaction from a DeductiveViewpoint. Artificial Intelligence, 35,401\u2013413, 1988.","journal-title":"Artificial Intelligence"},{"issue":"6","key":"1_CR3","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"H. L. Bodlaender","year":"1996","unstructured":"H. L. Bodlaender.A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305\u20131317, 1996.","journal-title":"SIAM Journal on Computing"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"A.K. Chandra and P.M. Merlin. Optimal Implementation of Conjunctive Queries in relational Databases. In ACM Symp. on Theory of Computing (STOC\u201977), pp.77\u201390, 1977.","DOI":"10.1145\/800105.803397"},{"key":"1_CR5","first-page":"161","volume":"87","author":"R.G. Downey","year":"1992","unstructured":"R.G. Downey and M.R. Fellows. Fixed ParameterTractability and Completeness. Congressus Numerantium, 87:161\u2013187, 1992.","journal-title":"Congressus Numerantium"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"R.G. Downey and M.R. Fellows. Fixed Parameter Intractability (Extended Abstract). In Proc. of Structure in Complexity Theory, IEEE, pp.36\u201350, 1992.","DOI":"10.1109\/SCT.1992.215379"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539792228228","volume":"24","author":"R.G. Downey","year":"1995","unstructured":"R.G. Downey and M.R. Fellows. Fixed Parameter Tractability and Completeness I: Basic Results. SIAM J. Comput., 24:873\u2013921, 1995.","journal-title":"SIAM J. Comput."},{"key":"1_CR8","unstructured":"R.G. Downey and M.R. Fellows. On the Parametric Complexity of Relational Database Queries and a Sharper Characterization of W[1]. In Combinatorics Complexity and Logics, Proceedings of DMTCS\u201996, pp.164\u2013213, Springer, 1996."},{"key":"1_CR9","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer, NewYork, 1999."},{"issue":"2","key":"1_CR10","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0304-3975(93)90073-3","volume":"114","author":"T. Eiter","year":"1993","unstructured":"T. Eiter and G. Gottlob. Propositional Circumscription and Extended ClosedWorld Reasoning are IIstackP stack2-complete. Theoretical Computer Science, 114(2):231\u2013245, 1993. Addendum 118:315.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"1_CR11","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1145\/261124.261126","volume":"22","author":"T. Eiter","year":"1997","unstructured":"T. Eiter, G. Gottlob, and H. Mannila. Disjunctive Datalog. ACM Trans. on Database Syst., 22(3):364\u2013418, September 1997.","journal-title":"ACM Trans. on Database Syst"},{"issue":"2","key":"1_CR12","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S. Fortune","year":"1980","unstructured":"S. Fortune, J.E. Hopcroft, and J. Wyllie. The Directed Subgraph Homeomorphism Problem. Theoretical Computer Science, 10(2): 111\u2013121, 1980.","journal-title":"Theoretical Computer Science"},{"key":"1_CR13","volume-title":"A Guide to the Theory of NPcompletenes","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability. A Guide to the Theory of NPcompleteness. Freeman and Comp., NY, USA, 1979."},{"key":"1_CR14","unstructured":"M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Logic Programming: Proc. Fifth Intl Conference and Symposium, pp. 1070\u20131080, Cambridge, Mass., 1988. MIT Press."},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, and F. Scarcello. The Complexity of Acyclic Conjunctive Queries. Technical Report DBAI-TR-98\/17, available on the web as: http:\/\/www.dbai.tuwien.ac.at\/staff\/gottlob\/acyclic.ps , or by email from the authors. An extended abstract concerning part of this work has been published in Proc. of the IEEE Symposium on Foundations of Computer Science (FOCS\u201998), pp.706\u2013715, Palo Alto, CA, 1998.","DOI":"10.1109\/SFCS.1998.743521"},{"key":"1_CR16","unstructured":"G. Gottlob, N. Leone, and F. Scarcello.AComparison of Structural CSP Decomposition Methods. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, pp. 394\u2013399, Stockholm, 1999."},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"P. Jeavons, D. Cohen, and M. Gyssens. Closure Properties of Constraints. JACM, 44(4), 1997.","DOI":"10.1145\/263867.263489"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"Ph. G. Kolaitis and M.Y. Vardi. Conjunctive-Query Containment and Constraint Satisfaction. Proc. of Symp. on Principles of Database Systems (PODS\u201998), 1998.","DOI":"10.1145\/275487.275511"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"C.H. Papadimitriou and M. Yannakakis. On the Complexity of Database Queries. In Proc. of Symp. on Principles of Database Systems (PODS\u201997), pp.12\u201319, Tucson, Arizona, 1997.","DOI":"10.1145\/263661.263664"},{"key":"1_CR20","first-page":"309","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph Minors II. Algorithmic Aspects of Tree-Width. J. Algorithms, 7:309\u2013322, 1986.","journal-title":"Algorithmic Aspects of Tree-Width. J. Algorithms"},{"key":"1_CR21","unstructured":"N. Robertson and P.D. Seymour. Graph Minors XX.Wagner\u2019s Conjecture. To appear."},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"M. Truszczy\u0144ski. Computing Large and Small Stable Models. In Proc. of the 16th International Conference on Logic Programming (ICLP\u201999), Las Cruces, New Mexico. To appear.","DOI":"10.1017\/S1471068402001138"},{"key":"1_CR23","doi-asserted-by":"crossref","unstructured":"M. Vardi. Complexity of Relational Query Languages. In Proceedings 14th STOC, pages 137\u2013146, San Francisco, 1982.","DOI":"10.1145\/800070.802186"},{"key":"1_CR24","unstructured":"M. Yannakakis. Algorithms for Acyclic Database Schemes. In Proc. of Int. Conf. on Very Large Data Bases (VLDB\u201981), pp. 82\u201394, C. Zaniolo and C. Delobel Eds., Cannes, France, 1981."}],"container-title":["Lecture Notes in Computer Science","Logic Programming and Nonmonotonic Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-46767-X_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T19:12:08Z","timestamp":1739992328000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-46767-X_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540667490","9783540467670"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-46767-x_1","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}