Ο φοιτητής του προγράμματος Χαράλαμπος Κωστόπουλος θα παρουσιάσει τη διπλωματική του εργασία με θέμα:
Η εκφραστικότητα της Datalog υψηλής τάξης με άρνηση
την Παρασκευή 20 Οκτωβρίου 2023 και ώρα 18:00, μέσω τηλεμετάδοσης *.
Σύνοψη Διπλωματικής:
Είναι γνωστό αποτέλεσμα στη βιβλιογραφία ότι η Datalog με την υπόθεση ότι οι βάσεις δεδομένων εισόδου είναι διατεταγμένες, μπορεί να εκφράσει όλα εκείνα τα ερωτήματα που ανήκουν στην κλάση πολυπλοκότητας PTIME. Πρόσφατα, αυτό το αποτέλεσμα επεκτάθηκε και σε προγράμματα Datalog υψηλής τάξης που δεν περιέχουν άρνηση και αποδείχτηκε ότι η εκφραστικότητα αυξάνεται αυστηρά καθώς αυξάνεται και η τάξη των προγραμμάτων. Αυτή η διπλωματική μελετάει την εκφραστικότητα προγραμμάτων υψηλής τάξης Datalog όταν επιτρέπουμε άρνηση. Πιο συγκεκριμένα παρουσιάζεται μια ανάλυση της εκφραστικότητας διαφόρων εκδόσεων της υψηλής τάξης Datalog όπου κάθε φορά επιτρέπουμε ένα υποσύνολο από χαρακτηριστικά όπως η άρνηση, μερικώς εφαρμοσμένες εκφράσεις ως ορίσματα και υπαρξιακές μεταβλητές υψηλής τάξης. Σε κάθε επιλογή τέτοιων χαρακτηριστικών μελετάμε την επίδραση της αύξησης της επιτρεπόμενης τάξης των προγραμμάτων στην εκφραστικότητα της γλώσσας.
Προκύπτει ότι η εκφραστικότητα δεν αυξάνεται περαιτέρω όταν εισάγουμε τον τελεστή της άρνησης. Αν όμως δεν επιτρέψουμε μερικώς εφαρμοσμένες εκφράσεις στα προγράμματά μας τότε υπάρχει σημαντική διαφορά. Οι μερικώς εφαρμοσμένες εκφράσεις στα προγράμματα δίνουν από μόνες τους την μέγιστη εκφραστικότητα της γλώσσας, ενώ αν απουσιάζουν χρειαζόμαστε άρνηση με υπαρξιακές μεταβλητές για να πετύχουμε την ίδια εκφραστικότητα. Σε όλες τις άλλες περιπτώσεις η εκφραστικότητα της γλώσσας πέφτει στην κλάση PTIME ανεξαρτήτως της τάξης που επιτρέπουμε να έχουν οι τύποι στα προγράμματά μας.
Η Επιτροπή,
Αρχοντία Γιαννοπούλου,
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ.
Χρήστος Νομικός,
Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής, Πανεπιστήμιο Ιωαννίνων
Παναγιώτης Ροντογιάννης (Συνεπιβλέπων),
Τμήμα Πληροφορικής και Τηλεπικοινωνιών, ΕΚΠΑ.
Άγγελος Χαραλαμπίδης (Επιβλέπων),
Τμήμα Πληροφορικής και Τηλεματικής, Χαροκόπειο Πανεπιστήμιο.
* Αν επιθυμείτε να παρακολουθήσετε, παρακαλούμε στείλτε e-mail στο prondo@di.uoa.gr ή στο kostbabis@di.uoa.gr για να ενημερωθείτε για τη διεύθυνση του meeting.