The Expressive Power of Higher-Order Datalog. Issue 5 (September 2019)

• Record Type: Journal Article
• Authors: CHARALAMBIDIS, ANGELOS; NOMIKOS, CHRISTOS; RONDOGIANNIS, PANOS
• Is Part Of: Theory and practice of logic programming. Volume 19:Issue 5/6(2019)
• Page Start: 925
• Page End: 940
• Publication Date: 2019-09
• Subjects: Datalog, -- Higher-Order Logic Programming, -- Descriptive Complexity Theory; Logic programming -- Periodicals; Artificial intelligence -- Computer programs -- Periodicals; Constraint programming (Computer science) -- Periodicals; 005.115
• DOI: 10.1017/S1471068419000279
• Languages: English
• ISSNs: 1471-0684

Abstract

Abstract: A classical result in descriptive complexity theory states that Datalog expresses exactly the class of polynomially computable queries on ordered databases (Papadimitriou1985 ; Grädel1992 ; Vardi1982 ; Immerman1986 ; Leivant1989 ). In this paper we extend this result to the case of higher-order Datalog. In particular, we demonstrate that on ordered databases, for all k ≥ 2, k -order Datalog captures ( k − 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.