{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:43:59Z","timestamp":1725493439586},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540664925"},{"type":"electronic","value":"9783540482420"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1999]]},"DOI":"10.1007\/3-540-48242-3_13","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T16:28:09Z","timestamp":1184603289000},"page":"201-222","source":"Crossref","is-referenced-by-count":1,"title":["On the Complexity of Single-Rule Datalog Queries"],"prefix":"10.1007","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"S. Aanderaa. On the Decision Problem for Formulas in which all Disjunctions are binary. Proc. of the 2nd Scandinavian Logic Symposium, pp. 1\u201318, North Holland Publishing Company, 1971.","DOI":"10.1016\/S0049-237X(08)70839-5"},{"issue":"6","key":"13_CR2","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1016\/0020-0190(89)90019-7","volume":"32","author":"S. Abiteboul","year":"1989","unstructured":"S. Abiteboul. Boundedness is undecidable for datalog programs with a single recursive rule. Information Processing Letters, 32(6):281\u2013289, 1989.","journal-title":"Information Processing Letters"},{"key":"13_CR3","unstructured":"S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995."},{"issue":"4","key":"13_CR4","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1145\/153724.153752","volume":"40","author":"F. Afrati","year":"1993","unstructured":"F. Afrati and C. H. Papadimitriou. The parallel complexity of simple logic programs. Journal of the Association for Computing Machinery, 40(4):891\u2013916, 1993.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"13_CR5","unstructured":"E. B\u00f6rger Reduktionstypen in Krom-und Hornformeln. Ph.D. Dissertation, Minister, Germany, 1971."},{"key":"13_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59207-2","volume-title":"The Classical Decision Problem","author":"E. B\u00f6rger","year":"1997","unstructured":"E. B\u00f6rger, E. Gr\u00e4del, and Y. Gurevich. The Classical Decision Problem. Springer, Berlin Heidelberg, 1997."},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"S. Ceri, G. Gottlob, and L. Tanca. Logic Programming and Databases. Surveys in Computer Science. Springer Verlag, 1990.","DOI":"10.1007\/978-3-642-83952-8"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, H. Lewis, and J. Makowsky. Embedded implicational dependencies and their inference problem. In ACM Symposium on Theory of Computing (STOC), pages 342\u2013354, 1981.","DOI":"10.1145\/800076.802488"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"A. Chandra and P. Merlin. Optimal implementation of conjunctive queries in relational databases. In Proc. Ninth ACM Symposium on the Theory of Computing, pages 77\u201390, 1977.","DOI":"10.1145\/800105.803397"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. In Proceedings Twelfth Annual IEEE Conference on Computational Complexity, pages 82\u2013101, Ulm, Germany, June 1997. Full version available from the authors.","DOI":"10.1109\/CCC.1997.612304"},{"key":"13_CR11","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1007\/3-540-56503-5_7","volume-title":"Proceedings Tenth Symposium on Theoretical Aspects of Computing (STACS-93)","author":"P. Devienne","year":"1993","unstructured":"P. Devienne, P. Leb\u00e8gue, and J.-C. Routier. Halting problem of one binary Horn clause is undecidable. In P. Enjalbert, A. Finkel, and K. Wagner, editors, Proceedings Tenth Symposium on Theoretical Aspects of Computing (STACS-93), number 665 in LNCS, pages 48\u201357, W\u00fcrzburg, February 1993. Springer."},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"H.-D. Ebbinghaus and J. Flum. Finite Model Theory. Perspectives in Mathematical Logic. Springer, 1995.","DOI":"10.1007\/978-3-662-03182-7"},{"key":"13_CR13","unstructured":"M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. 5th International Conference and Symposium on Logic Programming, pages 1070\u20131080. The MIT Press, 1988."},{"issue":"2","key":"13_CR14","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/0020-0190(87)90103-7","volume":"24","author":"G. Gottlob","year":"1987","unstructured":"G. Gottlob. Subsumption and implication. Information Processing Letters, 24(2):109\u2013111, 1987.","journal-title":"Information Processing Letters"},{"key":"13_CR15","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/BFb0020821","volume-title":"Proceedings STACS-91","author":"E. Gr\u00e4del","year":"1991","unstructured":"E. Gr\u00e4del. The Expressive Power of Second-Order Horn Logic. In Proceedings STACS-91, LNCS 480, pages 466\u2013477, 1991."},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","volume":"101","author":"E. Gr\u00e4del","year":"1992","unstructured":"E. Gr\u00e4del. Capturing Complexity Classes with Fragments of Second Order Logic. Theoretical Computer Science, 101:35\u201357, 1992.","journal-title":"Theoretical Computer Science"},{"key":"13_CR17","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."},{"issue":"5","key":"13_CR18","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0020-0190(93)90210-Z","volume":"45","author":"P. Hanschke","year":"1993","unstructured":"P. Hanschke and J. W\u00fcrtz. Satisfiability of the smallest binary program. Information Processing Utters, 45(5):237\u2013241, 1993.","journal-title":"Information Processing Utters"},{"issue":"2","key":"13_CR19","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1016\/0743-1066(95)00051-K","volume":"25","author":"G. G. Hillebrand","year":"1995","unstructured":"G. G. Hillebrand, P. C. Kanellakis, H. G. Mairson, and M. Y. Vardi. Undecidable boundedness problems for datalog programs. Journal of Logic Programming, 25(2):163\u2013190, 1995.","journal-title":"Journal of Logic Programming"},{"key":"13_CR20","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","volume":"68","author":"N. Immerman","year":"1986","unstructured":"N. Immerman. Relational queries computable in polynomial time. Information and Control, 68:86\u2013104, 1986.","journal-title":"Information and Control"},{"key":"13_CR21","doi-asserted-by":"crossref","unstructured":"N. Immerman. Descriptive Complexity Theory. Springer, 1998 (to appear).","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"13_CR22","doi-asserted-by":"crossref","unstructured":"P. Kanellakis. Logic programming and parallel complexity. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pp. 547\u2013586. Morgan Kaufmann, 1988.","DOI":"10.1016\/B978-0-934613-40-8.50018-X"},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/181668.181674","volume":"5","author":"J. U. Kietz","year":"1994","unstructured":"J. U. Kietz, S. Dzeroski. Inductive Logic Programming and Learnability. SIGART Bulletin 5(1), pp. 22\u201332,1994.","journal-title":"SIGART Bulletin"},{"issue":"2","key":"13_CR24","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1017\/S0022481200051409","volume":"46","author":"H. Lewis","year":"1976","unstructured":"H. Lewis. Krom Formulas with One Dyadic Predicate Letter. Journal of Symbolic Logic, 46(2):341\u2013362, 1976.","journal-title":"Journal of Symbolic Logic"},{"key":"13_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1007\/3-540-60922-9_35","volume-title":"ACM Symposium on Theory of Computing (STOC)","author":"J. Marcinkowski","year":"1996","unstructured":"J. Marcinkowski. The 3 frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG programs. In ACM Symposium on Theory of Computing (STOC), volume 1046 of Lecture Notes in Computer Science, pages 427\u2013438. Springer Verlag, 1996."},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"J. Marcinkowski. DATALOG SIRUPs uniform boundedness is undecidable. In Proc. IEEE Conference on Logic in Computer Science (LICS), pages 13\u201324. IEEE Computer Society Press, 1996.","DOI":"10.1109\/LICS.1996.561299"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"J. Marcinkowski and L. Pacholski. Undecidability of the Horn-clause implication problem. In Proc. IEEE International Conference of Foundations of Computer Science (FOCS), pages 354\u2013362. IEEE Computer Society Press, 1992.","DOI":"10.1109\/SFCS.1992.267755"},{"key":"13_CR28","doi-asserted-by":"publisher","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":"13_CR29","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/BF01762108","volume":"3","author":"J. D. Ullman","year":"1988","unstructured":"J. D. Ullman and A. van Gelder. Parallel complexity of logical query programs. Algorithmica, 3:5\u201342, 1988.","journal-title":"Algorithmica"},{"key":"13_CR30","unstructured":"J. Ullman. Database and Knowledge-Base Systems, volume I. Computer Science Press, 1988."},{"key":"13_CR31","unstructured":"J. Ullman. Database and Knowledge-Base Systems, volume II. Computer Science Press, 1989."},{"key":"13_CR32","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"}],"container-title":["Lecture Notes in Computer Science","Logic for Programming and Automated Reasoning"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48242-3_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T03:38:38Z","timestamp":1556681918000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48242-3_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1999]]},"ISBN":["9783540664925","9783540482420"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-48242-3_13","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1999]]}}}