The Expressive Power of Higher-order Datalog: An XSB Implementation

Graduate Thesis uoadl:2810771 201 Read counter

Unit:
Department of Informatics and Telecommunications
Πληροφορική
Deposit date:
2018-10-17
Year:
2018
Author:
PROTOPAPAS EVANGELOS
Supervisors info:
Παναγιώτης Ροντογιάννης, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
The Expressive Power of Higher-order Datalog: An XSB Implementation
Languages:
English
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
Index:
Yes
Number of index pages:
1
Contains images:
No
Number of references:
12
Number of pages:
36
Thesis-Protopapas.pdf (433 KB) Open in new window