National and Kapodistrian University of Athens
Αποκρισιμότητα και πολυπλοκότητα της τροπικής λογικής
Abstract
dc:descriptionΣτην παρούσα εργασία μελετάμε την τροπική λογική, με έμφαση στις εφαρμογές της στην επιστήμη των υπολογιστών. Ένας από τους σημαντικότερους λόγους για την ευρεία χρήση της τροπικής λογικής σε πολλούς τομείς της επιστήμης των υπολογιστών (και όχι μόνο) είναι η συμπεριφορά της ως προς την αποκρισιμότητα: η τροπική λογική είναι αποκρίσιμη και παραμένει αποκρίσιμη μετά από πολύ ισχυρές επεκτάσεις ενώ, ταυτόχρονα, είναι αρκετά εκφραστική για να είναι χρήσιμη στην πράξη. Μπορεί κανείς να αντιπαραβάλει αυτή τη συμπεριφορά με την αντίστοιχη της πρωτοβάθμιας λογικής, η οποία είναι εξαρχής μη-αποκρίσιμη. Επιπρόσθετα, παρόλο που η πολυπλοκότητα της τροπικής λογικής είναι θεωρητικά αρκετά υψηλή, στην πράξη είναι σπάνια τα προβλήματα που την εξαναγκάζουν να είναι τέτοια. Αρχικά παρουσιάζουμε σχετικά αποτελέσματα, και μετά προσπαθούμε να εξηγήσουμε αυτή τη συμπεριφορά θεωρώντας κατάλληλα θραύσματα της πρωτοβάθμιας λογικής, τα οποία εκφράζουν αποτελεσματικά το «πνεύμα» της τροπικής λογικής.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Κούρτης Γεώργιος
Rights
- Language dc:language
- Ελληνικά, Greek
Identifiers
dc:identifier.*- Identifier
- uoadl:1316314