Στο πλαίσιο της διοργάνωσης των σεμιναρίων του τμήματος θα πραγματοποιηθεί διαδικτυακά μέσω της εφαρμογής Ms Teams τη Δευτέρα 27/09/2021 και ώρα 11:00, ομιλία με τίτλο «Εκφραστική δύναμη των λογικών προγραμμάτων υψηλής τάξης χωρίς συναρτησιακά σύμβολα». Ομιλητής θα είναι ο  κ. Χρήστος Νομικός, Επίκουρος Καθηγητής, Τμήμα Μηχανικών Η/Υ & Πληροφορικής. Μπορείτε να παρακολουθήσετε την ομιλία μέσω του παρακάτω συνδέσμου: Link MsTeams

ΠΕΡΙΛΗΨΗ

Τα λογικά προγράμματα υψηλής τάξης βασίζονται στη λογική υψηλής τάξης και αποτελούν επέκταση των κλασικών λογικών προγραμμάτων. Στην επέκταση αυτή τα κατηγορήματα επιτρέπεται να δέχονται ως ορίσματα άλλα κατηγορήματα. Η χρήση κατηγορημάτων υψηλής τάξης δεν αυξάνει την υπολογιστική ισχύ των λογικών προγραμμάτων, καθώς τα προγράμματα πρώτης τάξης είναι ήδη Turing-complete, δηλαδή μπορούν να υπολογίσουν οποιαδήποτε μερική αναδρομική συνάρτηση. Συνεπώς για να διερευνήσουμε την επίδραση των χαρακτηριστικών υψηλής τάξης στα λογικά προγράμματα, εξετάζουμε την εκφραστική δύναμη προγραμμάτων τα οποία έχουν κάποια ειδική μορφή.

Ένα κλασικό αποτέλεσμα στην περιοχή της περιγραφικής πολυπλοκότητας είναι ότι η κλάση των γλωσσών τις οποίες μπορούμε να αποφασίσουμε χρησιμοποιώντας λογικά προγράμματα χωρίς συναρτησιακά σύμβολα, ταυτίζεται με την κλάση πολυπλοκότητας P. Στο πλαίσιο της ομιλίας θα παρουσιαστεί μια γενίκευση του παραπάνω αποτελέσματος. Συγκεκριμένα, θα  αποδειχθεί ότι  η κλάση των γλωσσών τις οποίες μπορούμε να αποφασίσουμε χρησιμοποιώντας λογικά προγράμματα οποιασδήποτε τάξης k>1 χωρίς συναρτησιακά σύμβολα ταυτίζεται με την κλάση πολυπλοκότητας (k-1)–EXP.