{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,28]],"date-time":"2022-04-28T12:27:01Z","timestamp":1651148821159},"publisher-location":"Berlin, Heidelberg","reference-count":36,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540578024","type":"print"},{"value":"9783540483359","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-57802-1_5","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:23:29Z","timestamp":1330262609000},"page":"83-103","source":"Crossref","is-referenced-by-count":6,"title":["Expressive power and complexity of disjunctive datalog under the stable model semantics"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Eiter","sequence":"first","affiliation":[]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[]},{"given":"Heikki","family":"Mannila","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,28]]},"reference":[{"key":"5_CR1","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar, J. Diaz, and J. Gabarr\u00f3. Structural Complexity I. Springer, 1988.","DOI":"10.1007\/978-3-642-97062-7"},{"key":"5_CR2","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/978-1-4615-3422-8_30","volume-title":"Computer Science","author":"J. Balc\u00e1zar","year":"1992","unstructured":"J. Balc\u00e1zar, A. Lozano, and J. Tor\u00e1n. The Complexity of Algorithmic Problems on Succinct Instances. In R. Baeta-Yates and U. Manber, editors, Computer Science, pages 351\u2013377. Plenum Press, New York, 1992."},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"S. Ceri, G. Gottlob, and L. Tanca. Logical Programming and Databases. Springer, 1990.","DOI":"10.1007\/978-3-642-83952-8"},{"key":"5_CR4","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(80)90032-X","volume":"21","author":"A. Chandra","year":"1980","unstructured":"A. Chandra and D. Harel. Computable Queries for Relational Databases. Journal of Computer and System Sciences, 21:156\u2013178, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0743-1066(85)90002-0","volume":"2","author":"A. Chandra","year":"1985","unstructured":"A. Chandra and D. Harel. Horn Clause Queries and Generalizations. Journal of Logic Programming, 2:1\u201315, 1985.","journal-title":"Journal of Logic Programming"},{"key":"5_CR6","unstructured":"C. C. Chang and H. J. Keisler. Model Theory. North-Holland, 2nd edition, 1973."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"T. Eiter and G. Gottlob. Complexity Aspects of Various Semantics for Disjunctive Databases. In Proceedings of the Twelth ACM SIGACT SIGMOD-SIGART Symposium on Principles of Database Systems (PODS-93), pages 158\u2013167, 1993.","DOI":"10.1145\/153850.153864"},{"key":"5_CR8","unstructured":"T. Eiter, G. Gottlob, and H. Mannila. Adding Disjunction to Datalog. Manuscript available from the authors, November 1993."},{"key":"5_CR9","unstructured":"R. Fagin. Generalized First-Order Spectra and Polynomial-Time Recognizable Sets. In R. M. Karp, editor, Complexity of Computation, pages 43\u201374. AMS, 1974."},{"key":"5_CR10","doi-asserted-by":"crossref","unstructured":"J. Fern\u00e1ndez and J. Minker. Semantics of Disjunctive Deductive Databases. In Proceedings of the International Conference on Database Theory (ICDT-92), pages 21\u201350, Berlin, October 1992.","DOI":"10.1007\/3-540-56039-4_31"},{"key":"5_CR11","first-page":"183","volume":"56","author":"H. Galperin","year":"1983","unstructured":"H. Galperin and A. Wigderson. Succinct Representations of Graphs. Information and Computation, 56:183\u2013198, 1983.","journal-title":"Information and Computation"},{"key":"5_CR12","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. S. Johnson. Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. W. H. Freeman, New York, 1979."},{"key":"5_CR13","unstructured":"Y. Gurevich. Logic and the Challenge of Computer Science. In E. B\u00f6rger, editor, Trends in Theoretical Computer Science, chapter 1. Computer Science Press, 1988."},{"key":"5_CR14","volume-title":"A Catalog of Complexity Classes. volume A of Handbook of Theoretical Computer Science","author":"D. S. Johnson","year":"1990","unstructured":"D. S. Johnson. A Catalog of Complexity Classes. volume A of Handbook of Theoretical Computer Science, chapter 2. Elsevier Science Publishers B.V. (North-Holland), 1990."},{"key":"5_CR15","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0022-0000(91)90033-2","volume":"43","author":"P. Kolaitis","year":"1991","unstructured":"P. Kolaitis and C. H. Papadimitriou. Why Not Negation By Fixpoint? Journal of Computer and System Sciences, 43:125\u2013144, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"5_CR16","volume-title":"Foundations of Disjunctive Logic Programming","author":"J. Lobo","year":"1992","unstructured":"J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, Cambridge, MA, 1992."},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"A. Lozano and J. Balc\u00e1zar. The Complexity of Graph Problems for Succinctly Represented Graphs. In Proceedings of the 15th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, number 411 in LNCS, pages 277\u2013286, Castle Rolduc, The Netherlands 1989.","DOI":"10.1007\/3-540-52292-1_20"},{"key":"5_CR18","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01786976","volume":"15","author":"J. Lynch","year":"1982","unstructured":"J. Lynch. Complexity Classes and Theories of Finite Models. Mathematical Systems Theory, 15:127\u2013144, 1982.","journal-title":"Mathematical Systems Theory"},{"key":"5_CR19","unstructured":"J. Makowsky. Model Theory and Computer Science: An Appetizer. In S. Abramsky, D. Gabbay, and T. Maibaum, editors, Handbook of Logic in Computer Science, volume I, chapter 6. Oxford University Press, 1992."},{"key":"5_CR20","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/BF01543477","volume":"5","author":"W. Marek","year":"1992","unstructured":"W. Marek, A. Nerode, and J. Remmel. A Theory of Nonmonotonic Rule Systems II. Annals of Mathematics and Artificial Intelligence, 5:229\u2013264, 1992.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"5_CR21","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/0168-0072(92)90069-C","volume":"56","author":"W. Marek","year":"1992","unstructured":"W. Marek, A. Nerode, and J. Remmel. How Complicated is the Set of Stable Models of a Recursive Logic Program? Annals of Pure and Applied Logic, 56:119, 1992.","journal-title":"Annals of Pure and Applied Logic"},{"issue":"3","key":"5_CR22","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1145\/116825.116836","volume":"38","author":"W. Marek","year":"1991","unstructured":"W. Marek and M. Truszczy\u0144ski. Autoepistemic Logic. Journal of the ACM, 38(3):588\u2013619, 1991.","journal-title":"Journal of the ACM"},{"key":"5_CR23","first-page":"37","volume-title":"Computing Intersection of Autoepistemic Expansions","author":"W. Marek","year":"1991","unstructured":"W. Marek and M. Truszczy\u0144ski. Computing Intersection of Autoepistemic Expansions. In Proceedings of the 1st Intl. Workshop on Logic Programming and Nonmonotonic Reasoning, pages 37\u201350, Washington DC, July 1991. MIT Press."},{"key":"5_CR24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0004-3702(80)90011-9","volume":"13","author":"J. McCarthy","year":"1980","unstructured":"J. McCarthy. Circumscription \u2014 A Form of Non-Monotonic Reasoning. Artificial Intelligence, 13:27\u201339, 1980.","journal-title":"Artificial Intelligence"},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"J. Minker. On Indefinite Data Bases and the Closed World Assumption. In Proceedings of the 6th Conference on Automated Deduction (CADE), pages 292\u2013308, 1982.","DOI":"10.1007\/BFb0000066"},{"key":"5_CR26","first-page":"181","volume":"71","author":"C. Papadimitriou","year":"1985","unstructured":"C. Papadimitriou and M. Yannakakis. A Note on Succinct Representations of Graphs. Information and Computation, 71:181\u2013185, 1985.","journal-title":"Information and Computation"},{"key":"5_CR27","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/B978-0-934613-40-8.50009-9","volume-title":"Foundations of Deductive Databases and Logic Programming","author":"T. Przymusinski","year":"1988","unstructured":"T. Przymusinski. On the Declarative and Procedural Semantics of Stratified Deductive Databases. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 193\u2013216. Morgan Kaufman, Washington DC, 1988."},{"key":"5_CR28","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BF03037171","volume":"9","author":"T. Przymusinski","year":"1991","unstructured":"T. Przymusinski. Stable Semantics for Disjunctive Programs. New Generation Computing, 9:401\u2013424, 1991.","journal-title":"New Generation Computing"},{"key":"5_CR29","unstructured":"D. Sacc\u00e0. Multiple Stable Models are Needed to Solve Unique Solution Problems. In Informal Proceedings of the Second Compulog Net Meeting on Knowledge Bases (CNKBS-93), Athens, April 1993."},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"J. Schlipf. The Expressive Powers of Logic Programming Semantics. Technical Report CIS-TR-90-3, Computer Science Department, University of Cincinnati, 1990. Submitted. A preliminary version of this paper appeared in: Proceedings PODS-90, pages 196\u2013204.","DOI":"10.1145\/298514.298564"},{"key":"5_CR31","first-page":"93","volume-title":"A Survey of Complexity and Undecidability Results in Logic Programming","author":"J. Schlipf","year":"1992","unstructured":"J. Schlipf. A Survey of Complexity and Undecidability Results in Logic Programming. In H. Blair, W. Marek, A. Nerode, and J. Remmel, editors, Informal Proceedings of the Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming, pages 93\u2013102, Washington DC, November 1992. Cornell University, Mathematical Sciences Institute."},{"issue":"6","key":"5_CR32","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1093\/logcom\/1.6.861","volume":"1","author":"I. Stewart","year":"1991","unstructured":"I. Stewart. Complete Problems Involving Boolean Labelled Structures and Projection Transactions. Journal of Logic and Computation, 1(6):861\u2013882, 1991.","journal-title":"Journal of Logic and Computation"},{"key":"5_CR33","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L. J. Stockmeyer","year":"1977","unstructured":"L. J. Stockmeyer. The Polynomial-Time Hierarchy. Theoretical Computer Science, 3:1\u201322, 1977.","journal-title":"Theoretical Computer Science"},{"key":"5_CR34","unstructured":"J. D. Ullman. Principles of Database and Knowledge Base Systems, volume 1. Computer Science Press, 1988."},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"M. Vardi. Complexity of relational query languages. In Proceedings of the 14th ACM SIGACT Symposium on Theory of Computing (STOC-82), pages 137\u2013146, 1982.","DOI":"10.1145\/800070.802186"},{"issue":"2","key":"5_CR36","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00244994","volume":"1","author":"A. Yahya","year":"1985","unstructured":"A. Yahya and L. Henschen. Deduction in Non-Horn Databases. Journal of Automated Reasoning, 1(2):141\u2013160, 1985.","journal-title":"Journal of Automated Reasoning"}],"container-title":["Lecture Notes in Computer Science","Management and Processing of Complex Data Structures"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57802-1_5.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:14:12Z","timestamp":1605647652000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57802-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540578024","9783540483359"],"references-count":36,"URL":"http:\/\/dx.doi.org\/10.1007\/3-540-57802-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"published":{"date-parts":[[1994]]}}}