Μονάδα:
Διαπανεπιστημιακό ΠΜΣ Λογική και Θεωρία Αλγορίθμων και ΥπολογισμούΒιβλιοθήκη Σχολής Θετικών Επιστημών
Ημερομηνία κατάθεσης:
2014-05-01
Συγγραφέας:
Κούρτης Γεώργιος
Στοιχεία επιβλεπόντων καθηγητών:
Κ. Κούτρας Επίκ. Καθηγητής Πανεπιστήμιο Πελοποννήσου (Επιβλέπων), Ε. Ζάχος Καθηγητής ΕΜΠ, Κ. Δημητρακόπουλος Καθηγητής ΕΚΠΑ, Π. Ροντογιάννης Αναπλ. Καθηγητής ΕΚΠΑ
Πρωτότυπος Τίτλος:
Αποκρισιμότητα και πολυπλοκότητα της τροπικής λογικής
Γλώσσες εργασίας:
Ελληνικά
Μεταφρασμένος τίτλος:
Decidability and complexity of modal logic
Περίληψη:
Στην παρούσα εργασία μελετάμε την τροπική λογική, με έμφαση στις εφαρμογές της
στην επιστήμη των υπολογιστών. Ένας από τους σημαντικότερους λόγους για την
ευρεία χρήση της τροπικής λογικής σε πολλούς τομείς της επιστήμης των
υπολογιστών (και όχι μόνο) είναι η συμπεριφορά της ως προς την αποκρισιμότητα:
η τροπική λογική είναι αποκρίσιμη και παραμένει αποκρίσιμη μετά από πολύ
ισχυρές επεκτάσεις ενώ, ταυτόχρονα, είναι αρκετά εκφραστική για να είναι
χρήσιμη στην πράξη. Μπορεί κανείς να αντιπαραβάλει αυτή τη συμπεριφορά με την
αντίστοιχη της πρωτοβάθμιας λογικής, η οποία είναι εξαρχής μη-αποκρίσιμη.
Επιπρόσθετα, παρόλο που η πολυπλοκότητα της τροπικής λογικής είναι θεωρητικά
αρκετά υψηλή, στην πράξη είναι σπάνια τα προβλήματα που την εξαναγκάζουν να
είναι τέτοια. Αρχικά παρουσιάζουμε σχετικά αποτελέσματα, και μετά προσπαθούμε
να εξηγήσουμε αυτή τη συμπεριφορά θεωρώντας κατάλληλα θραύσματα της
πρωτοβάθμιας λογικής, τα οποία εκφράζουν αποτελεσματικά το «πνεύμα» της
τροπικής λογικής.
Λέξεις-κλειδιά:
Τροπική λογική, Θεωρία υπολογισμού, Υπολογιστική πολυπλοκότητα, Θραύσματα πρωτοβάθμιας λογικής, Θραύσμα δύο-μεταβλητών
Αρ. σελίδων ευρετηρίου:
0
Αρ. βιβλιογραφικών αναφορών:
42
