{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:23:00Z","timestamp":1737091380037,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540721994"},{"type":"electronic","value":"9783540722007"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-72200-7_7","type":"book-chapter","created":{"date-parts":[[2007,6,5]],"date-time":"2007-06-05T16:54:47Z","timestamp":1181062487000},"page":"58-70","source":"Crossref","is-referenced-by-count":7,"title":["Complexity of Default Logic on Generalized Conjunctive Queries"],"prefix":"10.1007","author":[{"given":"Philippe","family":"Chapdelaine","sequence":"first","affiliation":[]},{"given":"Miki","family":"Hermann","sequence":"additional","affiliation":[]},{"given":"Ilka","family":"Schnoor","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"7_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0004-3702(02)00189-3","volume":"139","author":"R. Ben-Eliyahu-Zohary","year":"2002","unstructured":"Ben-Eliyahu-Zohary, R.: Yet some more complexity results for default logic. Artificial Intelligence\u00a0139(1), 1\u201320 (2002)","journal-title":"Artificial Intelligence"},{"key":"7_CR2","unstructured":"B\u00f6hler, E., et al.: Playing with Boolean blocks, parts\u00a0I and\u00a0II. SIGACT News, 34(4), 38\u201352 (2003) and 35(1), 22\u201335 (2004)"},{"key":"7_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"412","DOI":"10.1007\/3-540-45793-3_28","volume-title":"Computer Science Logic","author":"E. B\u00f6hler","year":"2002","unstructured":"B\u00f6hler, E., et al.: Equivalence and isomorphism for Boolean constraint satisfaction. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol.\u00a02471, pp. 412\u2013426. Springer, Heidelberg (2002)"},{"issue":"2","key":"7_CR4","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/j.ipl.2005.06.003","volume":"96","author":"E. B\u00f6hler","year":"2005","unstructured":"B\u00f6hler, E., et al.: Bases for Boolean co-clones. Information Processing Letters\u00a096(2), 59\u201366 (2005)","journal-title":"Information Processing Letters"},{"issue":"3","key":"7_CR5","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1137\/S0097539700376676","volume":"34","author":"A. Bulatov","year":"2005","unstructured":"Bulatov, A., Jeavons, P., Krokhin, A.: Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing\u00a034(3), 720\u2013742 (2005)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"7_CR6","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1109\/69.599933","volume":"9","author":"M. Cadoli","year":"1997","unstructured":"Cadoli, M., Eiter, T., Gottlob, G.: Default logic as a query language. IEEE Transactions on Knowledge and Data Engineering\u00a09(3), 448\u2013463 (1997)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"7_CR7","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718546","volume-title":"Complexity Classifications of Boolean Constraint Satisfaction Problems","author":"N. Creignou","year":"2001","unstructured":"Creignou, N., Khanna, S., Sudan, M.: Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM, Philadelphia (2001)"},{"key":"7_CR8","unstructured":"Creignou, N., Zanuttini, B.: A complete classification of the complexity of propositional abduction (Submitted October 2004)"},{"key":"7_CR9","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman, New York (1979)"},{"issue":"1","key":"7_CR10","doi-asserted-by":"crossref","first-page":"95","DOI":"10.2140\/pjm.1968.27.95","volume":"27","author":"D. Geiger","year":"1968","unstructured":"Geiger, D.: Closed systems of functions and predicates. Pacific Journal of Mathematics\u00a027(1), 95\u2013100 (1968)","journal-title":"Pacific Journal of Mathematics"},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1093\/logcom\/2.3.397","volume":"2","author":"G. Gottlob","year":"1992","unstructured":"Gottlob, G.: Complexity results for nonmonotonic logics. Journal of Logic and Computation\u00a02(3), 397\u2013425 (1992)","journal-title":"Journal of Logic and Computation"},{"issue":"4","key":"7_CR12","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1145\/263867.263489","volume":"44","author":"P. Jeavons","year":"1997","unstructured":"Jeavons, P., Cohen, D., Gyssens, M.: Closure properties of constraints. Journal of the Association for Computing Machinery\u00a044(4), 527\u2013548 (1997)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"1-3","key":"7_CR13","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1016\/0004-3702(91)90011-8","volume":"49","author":"H.A. Kautz","year":"1991","unstructured":"Kautz, H.A., Selman, B.: Hard problems for simple default logics. Artificial Intelligence\u00a049(1-3), 243\u2013279 (1991)","journal-title":"Artificial Intelligence"},{"issue":"1-4","key":"7_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/BF01531081","volume":"1","author":"W. Marek","year":"1990","unstructured":"Marek, W., Truszczy\u0144ski, M.: Modal logic for default reasoning. Annals of Mathematics and Artificial Intelligence\u00a01(1-4), 275\u2013302 (1990)","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"1-2","key":"7_CR15","doi-asserted-by":"crossref","first-page":"117","DOI":"10.3233\/FI-1992-171-208","volume":"17","author":"I. Niemel\u00e4","year":"1992","unstructured":"Niemel\u00e4, I.: On the decidability and complexity of autoepistemic reasoning. Fundamenta Informaticae\u00a017(1-2), 117\u2013155 (1992)","journal-title":"Fundamenta Informaticae"},{"key":"7_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/978-3-540-32275-7_18","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"G. Nordh","year":"2005","unstructured":"Nordh, G.: A trichotomy in the complexity of propositional circumscription. In: Baader, F., Voronkov, A. (eds.) LPAR 2004. LNCS (LNAI), vol.\u00a03452, pp. 257\u2013269. Springer, Heidelberg (2005)"},{"key":"7_CR17","unstructured":"Nordh, G., Zanuttini, B.: Propositional abduction is almost always hard. In: Kaelbling, L.P., Saffiotti, A. (eds.) Proc. 19th IJCAI, Edinburgh, UK, pp. 534\u2013539 (2005)"},{"key":"7_CR18","volume-title":"Theories of Computability","author":"N. Pippenger","year":"1997","unstructured":"Pippenger, N.: Theories of Computability. Cambridge University Press, Cambridge (1997)"},{"key":"7_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-5547-1","volume-title":"Funktionen- und Relationenalgebren","author":"R. P\u00f6schel","year":"1979","unstructured":"P\u00f6schel, R., Kalu\u017enin, L.A.: Funktionen- und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin (1979)"},{"key":"7_CR20","first-page":"1","volume":"5","author":"E.L. Post","year":"1941","unstructured":"Post, E.L.: The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies\u00a05, 1\u2013122 (1941)","journal-title":"Annals of Mathematical Studies"},{"issue":"1-2","key":"7_CR21","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0004-3702(80)90014-4","volume":"13","author":"R. Reiter","year":"1980","unstructured":"Reiter, R.: A logic for default reasoning. Artificial Intelligence\u00a013(1-2), 81\u2013132 (1980)","journal-title":"Artificial Intelligence"},{"key":"7_CR22","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proc. 10th Symposium on Theory of Computing (STOC\u201978), San Diego, California, USA, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"key":"7_CR23","unstructured":"Stillman, J.: It\u2019s not my default: the complexity of membership problems in restricted propositional default logics. In: Proc. 8th AAAI, Boston, MA, USA, pp. 571\u2013578 (1990)"},{"key":"7_CR24","unstructured":"Stillman, J.: The complexity of propositional default logics. In: Proc. 10th AAAI, San Jose, California, USA, July 1992, pp. 794\u2013799 (1992)"},{"issue":"1","key":"7_CR25","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1976","unstructured":"Wrathall, C.: Complete sets and the polynomial-time hierarchy. Theoretical Computer Science\u00a03(1), 23\u201333 (1976)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"7_CR26","doi-asserted-by":"crossref","first-page":"393","DOI":"10.3233\/FUN-2001-45406","volume":"45","author":"X. Zhao","year":"2001","unstructured":"Zhao, X., Ding, D.: Complexity results for 2CNF default theories. Fundamenta Informaticae\u00a045(4), 393\u2013404 (2001)","journal-title":"Fundamenta Informaticae"}],"container-title":["Lecture Notes in Computer Science","Logic Programming and Nonmonotonic Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-72200-7_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T23:47:00Z","timestamp":1737071220000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-72200-7_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540721994","9783540722007"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-72200-7_7","relation":{},"subject":[]}}