Εφαρμογή της θεωρίας του λογικού προγραμματισμου στη σημασιολογία των μη-μονοτονικών τυπικών γραμματικών

Οι Boolean γραμματικές [A. Okhotin, Information and Computation 194 (1) (2004) 19-48] είναι μια πολλά υποσχόμενη επέκταση των γραμματικών χωρίς συμφραζόμενα η οποία υποστηρίζει σύζευξη και άρνηση στα σώματα των κανόνων. Στη διατριβή αυτή δίνουμε την πρώτη ολοκληρωμένη ανάλυση της σημασιολογίας των Boolean γραμματικών, δηλαδή μια σημασιολογία που εφαρμόζεται σε όλες αυτές τις γραμματικές. Η βασική ιδέα της πρότασής μας έρχεται από το χώρο της άρνησης στο λογικό προγραμματισμό και συγκεκριμένα τη well-founded σημασιολογία η οποία είναι αποδεκτή στο χώρο ως η “σωστή” προσέγγιση στην άρνηση. Αποδεικνύουμε ότι για κάθε Boolean γραμματική υπάρχει μια διακεκριμένη (τρίτιμη) ερμηνεία των μη τερματικών συμβόλων η οποία ικανοποιεί όλους τους κανόνες της γραμματικής και ταυτόχρονα είναι το ελάχιστο σταθερό σημείο ενός τελεστή σχετικού με τη γραμματική. Στη συνέχεια, δείχνουμε ότι κάθε Boolean γραμματική μπορεί να μετασχηματιστεί σε μια ισοδύναμη (υπό τη νέα σημασιολογία) κανονική μορφή. Με βάση αυτήν την κανονική μορφή, προτείνουμε έναν O(n³) αλγόριθμο parsing για κάθε Boolean γραμματική σε κανονική μορφή. Συνοψίζοντας, η πρώτη συνεισφορά της διατριβής αυτής είναι μια σημασιολογία που ενώ εφαρμόζεται σε όλες τις Boolean γραμματικές, διατηρεί την πολυπλοκότητα του parsing που σχετίζεται με τέτοιου είδους γραμματικές. Η δεύτερη συνεισφορά της διατριβής αυτής είναι ένας καθαρά παιγνιοθεωρητικός χαρακτηρισμός των Boolean γραμματικών. Συγκεκριμένα, προτείνουμε ένα άπειρο παίγνιο πλήρους πληροφορίας δύο παικτών για Boolean γραμματικές που είναι ισοδύναμο με τη well-founded σημασιολογία τους. Το παίγνιο είναι εφαρμόσιμο άμεσα και στις πιο απλές κλάσεις των συζευκτικών και χωρίς συμφραζόμενα γραμματικών ενώ παράλληλα προσφέρει μια νέα πολλά υποσχόμενη σύνδεση της θεωρίας παιγνίων και των τυπικών γλωσσών.