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

Abstract

Boolean grammars [A. Okhotin, Information and Computation 194(1) (2004) 19-48] are a promising extension of context-free grammars that supports conjunction and negation in rule bodies. In this dissertation we give the first proper mathematical treatment of the semantics of Boolean grammars, i.e. a semantics that applies to all such grammars, independently of their syntax. The key idea of our proposal comes from the area of negation in logic programming, and in particular from the so-called well-founded semantics which is widely accepted in this area to be the “correct” approach to negation. We show that for every Boolean grammar there exists a distinguished (three-valued) interpretation of the non-terminal symbols, which satisfies all the rules of the grammar and at the same time is the least fixed-point of an operator associated with the grammar. Then, we demonstrate that every Boolean grammar can be transformed into an equivalent (under the new semantics) grammar in normal form. Based on this normal form, we propose an Ο(n³) algorithm for parsing that applies to any such normalized Boolean grammar. In summary, the first contribution of this dissertation is to provide a semantics which applies to all Boolean grammars while at the same time retaining the complexity of parsing associated with this type of grammars. The second contribution of the dissertation is a purely game-theoretic characterization of Boolean grammars. In particular, we propose a two player infinite game of perfect information for Boolean grammars, which is equivalent to their well-founded semantics. The game is directly applicable to the simpler classes of conjunctive and context-free grammars, and it offers a promising new connection between game theory and formal languages.

Οι 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 σημασιολογία τους. Το παίγνιο είναι εφαρμόσιμο άμεσα και στις πιο απλές κλάσεις των συζευκτικών και χωρίς συμφραζόμενα γραμματικών ενώ παράλληλα προσφέρει μια νέα πολλά υποσχόμενη σύνδεση της θεωρίας παιγνίων και των τυπικών γλωσσών.