Unit:
Department of Informatics and TelecommunicationsΠληροφορική
Author:
PROTOPAPAS EVANGELOS
Supervisors info:
Παναγιώτης Ροντογιάννης, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
The Expressive Power of Higher-order Datalog: An XSB Implementation
Translated title:
The Expressive Power of Higher-order Datalog: An XSB Implementation
Summary:
This thesis follows the results in the yet unpublished paper of A. Charalambidis, Ch. Nomikos and P. Rondogiannis namely “The Expressive Power of Higher-order Datalog”. That paper proposes a proof which shows that Higher-order Datalog is equivalent in computational power to exponentially time bounded Turing Machines. In other words that higher-order Datalog captures the complexity class of decision problems EXP^(k)TIME. This thesis will review the above result in detail while demonstrating and proposing solutions for the flaws in the programs written in that paper. In addition a working implementation of the programs in the XSB system will be provided which shows that the proposed results hold.
Main subject category:
Science
Keywords:
Higher-order Datalog, Expressivity, Complexity Theory, Turing machine simulation