{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:25:24Z","timestamp":1756383924460,"version":"3.40.5"},"reference-count":18,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T00:00:00Z","timestamp":1568937600000},"content-version":"unspecified","delay-in-days":19,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A classical result in descriptive complexity theory states that Datalog expresses exactly the class of polynomially computable queries on ordered databases (Papadimitriou 1985; Gr\u00e4del 1992; Vardi 1982; Immerman 1986; Leivant 1989). In this paper we extend this result to the case of higher-order Datalog. In particular, we demonstrate that on ordered databases, for all <jats:italic>k<\/jats:italic> \u2265 2, <jats:italic>k<\/jats:italic>-order Datalog captures (<jats:italic>k<\/jats:italic> \u2212 1)-EXPTIME. This result suggests that higher-order extensions of Datalog possess superior expressive power and they are worthwhile of further investigation both in theory and in practice.<\/jats:p>","DOI":"10.1017\/s1471068419000279","type":"journal-article","created":{"date-parts":[[2019,9,20]],"date-time":"2019-09-20T09:06:21Z","timestamp":1568970381000},"page":"925-940","source":"Crossref","is-referenced-by-count":3,"title":["The Expressive Power of Higher-Order Datalog"],"prefix":"10.1017","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7437-410X","authenticated-orcid":false,"given":"ANGELOS","family":"CHARALAMBIDIS","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CHRISTOS","family":"NOMIKOS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"PANOS","family":"RONDOGIANNIS","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2019,9,20]]},"reference":[{"key":"S1471068419000279_ref7","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0304-3975(92)90149-A","article-title":"Capturing complexity classes by fragments of second-order logic","volume":"1","author":"Gr\u00e4del","year":"1992","journal-title":"Theoretical Computer Science 101"},{"key":"S1471068419000279_ref11","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0022-0000(89)90019-6","article-title":"Descriptive characterizations of computational complexity","volume":"1","author":"Leivant","year":"1989","journal-title":"Journal of Computer and System Science 39"},{"key":"S1471068419000279_ref13","unstructured":"Lovren\u010di\u0107, A. and \u010cubrilo, M. 1999. Amalgamation of heterogeneous data sources using amalgamated annotated hilog. In 3rd international IEEE Conference on Intelligent Engineering Systems (INES\u201999)."},{"key":"S1471068419000279_ref15","unstructured":"Papadimitriou, C. H. 1985. A note on the expressive power of prolog. Bulletin of the EATCS 26, 21\u201322."},{"key":"S1471068419000279_ref14","doi-asserted-by":"crossref","unstructured":"Miller, D. and Nadathur, G. 1986. Higher-order logic programming. In Proceedings of the Third International Conference on Logic Programming (ICLP). 448\u2013462.","DOI":"10.1007\/3-540-16492-8_94"},{"key":"S1471068419000279_ref8","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/S0019-9958(86)80029-8","article-title":"Relational queries computable in polynomial time","volume":"1","author":"Immerman","year":"1986","journal-title":"Information and Control 68"},{"key":"S1471068419000279_ref12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-83189-8","volume-title":"Foundations of Logic Programming","author":"Lloyd","year":"1987"},{"key":"S1471068419000279_ref5","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0743-1066(93)90039-J","article-title":"HILOG: A foundation for higher-order logic programming","volume":"3","author":"Chen","year":"1993","journal-title":"Journal of Logic Programming 15"},{"key":"S1471068419000279_ref3","first-page":"421","article-title":"Approximation fixpoint theory and the well-founded semantics of higher-order logic programs","volume":"3","author":"Charalambidis","year":"2018","journal-title":"TPLP 18"},{"key":"S1471068419000279_ref18","first-page":"671","volume-title":"OTM Confederated International Conferences \u201cOn the Move to Meaningful Internet Systems\u201d","volume":"2888","author":"Yang","year":"2003"},{"key":"S1471068419000279_ref1","first-page":"395","volume-title":"Logic Programming: The 1999 International Conference, Las Cruces, New Mexico, USA, November 29 - December 4, 1999","author":"Bezem","year":"1999"},{"key":"S1471068419000279_ref2","first-page":"21","article-title":"Extensional higher-order logic programming","volume":"3","author":"Charalambidis","year":"2013","journal-title":"ACM Trans. on Computational Logic 14"},{"key":"S1471068419000279_ref4","unstructured":"Charalambidis, A. , Rondogiannis, P. , and Troumpoukis, A. 2018. Higher-order logic programming: An expressive language for representing qualitative preferences. Science of Computer Programming 155, 173\u2013197."},{"key":"S1471068419000279_ref6","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502810"},{"key":"S1471068419000279_ref9","first-page":"5","article-title":"The expressive power of higher-order types or, life without CONS","volume":"1","author":"Jones","year":"2001","journal-title":"Journal of Functional Programming 11"},{"key":"S1471068419000279_ref16","first-page":"137","volume-title":"Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982","author":"Vardi","year":"1982"},{"key":"S1471068419000279_ref17","first-page":"289","volume-title":"Logic Programming, Proceedings of the 1991 International Symposium","author":"Wadge","year":"1991"},{"key":"S1471068419000279_ref10","unstructured":"Kountouriotis, V. , Rondogiannis, P. , and Wadge, W. W. 2005. Extensional higher-order datalog. In Short Paper Proceedings of the 12th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR). 1\u20135."}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068419000279","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T04:34:10Z","timestamp":1571114050000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068419000279\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":18,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["S1471068419000279"],"URL":"https:\/\/doi.org\/10.1017\/s1471068419000279","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}