{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,4]],"date-time":"2026-10-04T01:21:34Z","timestamp":1791076894514,"version":"4.1.0"},"reference-count":34,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2003,5,1]],"date-time":"2003-05-01T00:00:00Z","timestamp":1051747200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":3730,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information and Computation"],"published-print":{"date-parts":[[2003,5]]},"DOI":"10.1016\/s0890-5401(03)00012-9","type":"journal-article","created":{"date-parts":[[2003,5,12]],"date-time":"2003-05-12T23:55:41Z","timestamp":1052783741000},"page":"104-122","source":"Crossref","is-referenced-by-count":32,"title":["On the complexity of single-rule datalog queries"],"prefix":"10.1016","volume":"183","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Papadimitriou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/S0890-5401(03)00012-9_BIB1","series-title":"Proc. of the 2nd Scandinavian Logic Symposium","first-page":"1","article-title":"On the decision problem for formulas in which all disjunctions are binary","author":"Aanderaa","year":"1971"},{"issue":"6","key":"10.1016\/S0890-5401(03)00012-9_BIB2","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(89)90019-7","article-title":"Boundedness is undecidable for datalog programs with a single recursive rule","volume":"32","author":"Abiteboul","year":"1989","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0890-5401(03)00012-9_BIB3","series-title":"Foundations of Databases","author":"Abiteboul","year":"1995"},{"issue":"4","key":"10.1016\/S0890-5401(03)00012-9_BIB4","doi-asserted-by":"crossref","first-page":"891","DOI":"10.1145\/153724.153752","article-title":"The parallel complexity of simple logic programs","volume":"40","author":"Afrati","year":"1993","journal-title":"J. Assoc. Comput. Mach."},{"key":"10.1016\/S0890-5401(03)00012-9_BIB5","unstructured":"E. B\u00f6rger, Reduktionstypen in Krom- und Hornformeln, Ph.D. Dissertation, M\u00fcnster, Germany, 1971"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB6","series-title":"Logic Programming and Databases. Surveys in Computer Science","author":"Ceri","year":"1990"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB7","doi-asserted-by":"crossref","unstructured":"A.K. Chandra, H. Lewis. J. Makowsky, Embedded implicational dependencies and their inference problem, in: ACM Symposium on Theory of Computing (STOC), 1981, pp. 342\u2013354","DOI":"10.1145\/800076.802488"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB8","doi-asserted-by":"crossref","unstructured":"A. Chandra, P. Merlin, Optimal implementation of conjunctive queries in relational databases, in: Proc. Ninth ACM Symposium on the Theory of Computing, 1977, pp. 77\u201390","DOI":"10.1145\/800105.803397"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB9","doi-asserted-by":"crossref","unstructured":"E. Dantsin, T. Eiter, G. Gottlob, A. Voronkov, Complexity and expressive power of logic programming, in: Proceedings Twelfth Annual IEEE Conference on Computational Complexity. Ulm, Germany, June 1997, pp. 82\u2013101. Full version in ACM Computing Surveys 33 (3) (2001) 374\u2013425","DOI":"10.1145\/502807.502810"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB10","first-page":"48","article-title":"Halting problem of one binary Horn clause is undecidable","volume":"vol. 665","author":"Devienne","year":"1993"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB11","series-title":"Finite Model Theory, Perspectives in Mathematical Logic","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03182-7","author":"Ebbinghaus","year":"1995"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB12","series-title":"Proc. 5th International Conference and Symposium on Logic Programming","first-page":"1070","article-title":"The stable model semantics for logic programming","author":"Gelfond","year":"1988"},{"issue":"2","key":"10.1016\/S0890-5401(03)00012-9_BIB13","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(87)90103-7","article-title":"Subsumption and implication","volume":"24","author":"Gottlob","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0890-5401(03)00012-9_BIB14","series-title":"Proceedings STACS-91","first-page":"466","article-title":"The expressive power of second-order horn logic","volume":"vol. 480","author":"Gr\u00e4del","year":"1991"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB15","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","article-title":"Capturing complexity classes with fragments of second order logic","volume":"101","author":"Gr\u00e4del","year":"1992","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0890-5401(03)00012-9_BIB16","series-title":"Trends in Theoretical Computer Science","article-title":"Logic and the Challenge of Computer Science","author":"Gurevich","year":"1988"},{"issue":"5","key":"10.1016\/S0890-5401(03)00012-9_BIB17","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0020-0190(93)90210-Z","article-title":"Satisfiability of the smallest binary program, Inform","volume":"45","author":"Hanschke","year":"1993","journal-title":"Process. Lett."},{"issue":"2","key":"10.1016\/S0890-5401(03)00012-9_BIB18","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0743-1066(95)00051-K","article-title":"Undecidable boundedness problems for datalog programs","volume":"25","author":"Hillebrand","year":"1995","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB19","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","article-title":"Relational queries computable in polynomial time","volume":"68","author":"Immerman","year":"1986","journal-title":"Inform. Control"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB20","series-title":"Descriptive Complexity, Graduate Texts in Computer Science","author":"Immerman","year":"1999"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB21","series-title":"Foundations of Deductive Databases and Logic Programming","first-page":"547","article-title":"Logic programming and parallel complexity","author":"Kanellakis","year":"1988"},{"issue":"1","key":"10.1016\/S0890-5401(03)00012-9_BIB22","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/181668.181674","article-title":"Inductive logic programming and learnability","volume":"5","author":"Kietz","year":"1994","journal-title":"SIGART Bull."},{"issue":"2","key":"10.1016\/S0890-5401(03)00012-9_BIB23","doi-asserted-by":"crossref","first-page":"341","DOI":"10.2307\/2272233","article-title":"Krom formulas with one dyadic predicate letter","volume":"46","author":"Lewis","year":"1976","journal-title":"J. Symbol. Logic"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB24","series-title":"ACM Symposium on Theory of Computing (STOC)","first-page":"427","article-title":"The 3 Frenchmen method proves undecidability of the uniform boundedness for single recursive rule ternary DATALOG programs","volume":"vol. 1046","author":"Marcinkowski","year":"1996"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB25","series-title":"Proc. IEEE Conference on Logic in Computer Science (LICS)","first-page":"13","article-title":"DATALOG SIRUPs uniform boundedness is undecidable","author":"Marcinkowski","year":"1996"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB26","series-title":"Proc. IEEE International Conference of Foundations of Computer Science (FOCS)","first-page":"354","article-title":"Undecidability of the Horn-clause implication problem","author":"Marcinkowski","year":"1992"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB27","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1006\/jcss.1995.1053","article-title":"The expressive powers of logic programming semantics","volume":"51","author":"Schlipf","year":"1995","journal-title":"J. Comput. Syst. Sci."},{"key":"10.1016\/S0890-5401(03)00012-9_BIB28","doi-asserted-by":"crossref","unstructured":"O. Shmueli, Decidability and expressiveness aspects of logic queries, in: Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS\u2019 87), March 23\u201325, San Diego, California. Assoc. Comput. Mach, ISBN 0-89791-223-3, 1987","DOI":"10.1145\/28659.28685"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB29","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01762108","article-title":"Parallel complexity of logical query programs","volume":"3","author":"Ullman","year":"1988","journal-title":"Algorithmica"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB30","volume":"vol. 1","author":"Ullman","year":"1988"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB31","volume":"vol. 2","author":"Ullman","year":"1989"},{"key":"10.1016\/S0890-5401(03)00012-9_BIB32","doi-asserted-by":"crossref","unstructured":"M. Vardi, Complexity of relational query languages, in: Proceedings 14th STOC, San Francisco, 1982, pp. 137\u2013146","DOI":"10.1145\/800070.802186"},{"key":"10.1016\/S0890-5401(03)00012-9_FR1","series-title":"The Classical Decision Problem","author":"B\u00f6rger","year":"1997"},{"key":"10.1016\/S0890-5401(03)00012-9_FR2","first-page":"3,1","article-title":"The polynomial-time hierarchy","author":"Stockmeyer","year":"1977","journal-title":"Theoret. Comput. Sci."}],"container-title":["Information and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540103000129?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0890540103000129?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T05:24:34Z","timestamp":1584509074000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0890540103000129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,5]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2003,5]]}},"alternative-id":["S0890540103000129"],"URL":"https:\/\/doi.org\/10.1016\/s0890-5401(03)00012-9","relation":{},"ISSN":["0890-5401"],"issn-type":[{"value":"0890-5401","type":"print"}],"subject":[],"published":{"date-parts":[[2003,5]]}}}