Unit:
Department of Informatics and TelecommunicationsΠληροφορική
Author:
ASLANIS-PETROU ROMANOS
Supervisors info:
Ροντογιάννης Παναγιώτης, Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών.
Άγγελος Χαραλαμπίδης, Επίκουρος Καθηγητής, Τμήμα Πληροφορικής και Τηλεματικής, Χαροκόπειο Πανεπιστήμιο
Original Title:
The expressive power of second-order datalog under the well-founded semantics of negation
Translated title:
The expressive power of second-order datalog under the well-founded semantics of negation
Summary:
It was recently shown that higher-order positive datalog captures the complexity class
(k − 1)-EXPTIME on ordered databases, and in particular for k = 2, second order datalog captures EXPTIM E. In this thesis we investigate the expressive power of second-order datalog under the well-founded semantics. More specifically, we present a recursive algorithm that takes as input an existential second-order logic formula φ and constructs a second-order WFS datalog program Pφ . Furthermore there is an equivalence, in terms of satisfiability, between the finite models of φ and the well-founded model of Pφ , that implies a correct behaviour of the constructed program. In other words, the satisfaction of a given SO(∃) formula by a structure is reduced into the satisfaction of the well-founded model of Pφ . As a result, by the well-known theorem of Fagin and the above transformation we deduce that second-order WFS datalog captures NP. Finally this result is not strict, meaning that it is possible that second-order WFS datalog is stronger, and does not depend upon any ordering assumption since SO(∃) is powerful enough to nondeterministically guess such an ordering.
Main subject category:
Technology - Computer science
Keywords:
Higher-order logic programming, second-order datalog, descriptive complexity theory
