Λογική και Πληροφορική ΙΙ : Λογική, Αυτόματα και Παίγνια
| Κωδικός | 711 |
|---|---|
| Εξάμηνο | Εαρινό |
| Ώρες Διδασκαλίας - Ώρες Εργαστηρίου | 4 - 0 |
| Διδάσκοντες | Ευστάθιος Ζάχος, Πέτρος Ποτίκας (Ε.ΔΙ.Π.) |
| Σύνδεσμοι | Ιστοσελίδα Μαθήματος |
| Πλατφόρμα Διδασκαλίας |
Τμήμα 1:
Webex
|
Περιγραφή
Σε αυτό το μάθημα θα διερευνήσουμε περιπτώσεις της αλληλεπίδρασης μεταξύ της Λογική, της Θεωρία Αυτομάτων και παιγνίων. Στη Θεωρία Πεπερασμένων Μοντέλων, θα εξετάσουμε τα παιχνίδια Ehrenfeucht-Fraisse και παραλλαγές τους και τι μας λένε για την εκφραστικότητα της πρωτοβάθμιας λογικής και άλλων λογικών. Θα εξηγήσουμε την ισοδυναμία μεταξύ MSO και αυτομάτων σε σχέση με τις γλώσσες που μπορούν να περιγράψουν και πώς αυτό οδηγεί στο θεώρημα του Courcelle, ένα σημαντικό αποτέλεσμα της θεωρίας παραμετρικής πολυπλοκότητας. Θα δούμε πώς το bisimulation, μια σημαντική έννοια για υπολογιστικές διαδικασίες που μπορεί να θεωρηθεί και παιχνίδι, χαρακτηρίζει την τροπική λογική (modal logic) ως ένα κομμάτι της πρωτοβάθμιας λογικής. Ένα μεγάλο μέρος του μαθήματος θα επικεντρωθεί σε παιχνίδια άπειρων κινήσεων, τα οποία μπορούν να περιγράψουν τη συμπεριφορά αυτομάτων σε άπειρες λέξεις / δέντρα / γραφήματα, τα οποία, με τη σειρά τους, μπορούν να αποτελέσουν σημασιολογία για τον μ-λογισμό (μ-calculus), μια σημαντική τροπική λογική σταθερών σημείων. Χρησιμοποιώντας τα εργαλεία που θα αναπτύξουμε στο μάθημα, καταλήγουμε με αποτελέσματα υπολογισιμότητας για διάφορες λογικές θεωρίες σε άπειρες δομές.