Μονάδα:
Τμήμα Πληροφορικής & ΤηλεπικοινωνιώνΠληροφορική
Ημερομηνία κατάθεσης:
2018-10-17
Συγγραφέας:
ΠΡΩΤΟΠΑΠΑΣ ΕΥΑΓΓΕΛΟΣ
Στοιχεία επιβλεπόντων καθηγητών:
Παναγιώτης Ροντογιάννης, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Πρωτότυπος Τίτλος:
The Expressive Power of Higher-order Datalog: An XSB Implementation
Γλώσσες εργασίας:
Αγγλικά
Μεταφρασμένος τίτλος:
Η Εκφραστική Ισχύς της Datalog Υψηλής-τάξης: Μία Υλοποίηση στο XSB
Περίληψη:
Η πτυχιακή εργασία ακολουθεί τα αποτελέσματα του μη δημοσιευμένου ακόμα άρθρου των, Α. Χαραλαμπίδη, Χ. Νομικού και Π. Ροντογιάννη με τίτλο “The Expressive Power of Higher-order Datalog”. Το άρθρο παρουσιάζει μία απόδειξη ισοδυναμίας σε εκφραστική ισχύ της Datalog υψηλής-τάξης, με τις χρονικά εκθετικά περιορισμένες μηχανές Turing. Με άλλα λόγια ότι η Datalog υψηλής-τάξης εκφράζει τις κλάσεις πολυπλοκότητας των προβλημάτων απόφασης EXP^(k)TIME. Η πτυχιακή εργασία αυτή, θα παρουσιάσει με λεπτομέρεια τα παραπάνω αποτελέσματα, καθώς και θα υποδείξει κάποια σφάλματα στα προγράμματα που αναγράφονται στο άρθρο, καθώς και θα προτείνει τρόπους επίλυσής τους. Επιπλέον θα παρατεθεί μία λειτουργική υλοποίηση των προγραμμάτων στο σύστημα XSB, με στόχο την τεκμηρίωση των παραπάνω αποτελεσμάτων.
Κύρια θεματική κατηγορία:
Θετικές Επιστήμες
Λέξεις-κλειδιά:
Datalog υψηλής τάξης, Εκφραστικότητα, Θεωρία πολυπλοκότητας, Εξομοίωση μηχανής Turing
Αρ. σελίδων ευρετηρίου:
1
Αρ. βιβλιογραφικών αναφορών:
12
