Σημασιολογικές προσεγγίσεις για γραμματικές με λογικούς τελεστές
Φόρτωση...
Ημερομηνία
Συγγραφείς
Παπαδογιάννης, Παύλος
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
Στην παρούσα διατριβή μελετώνται δύο σημασιολογίες για τις γραμματικές με λογικούς
τελεστές μέσω διαφορετικών χαρακτηρισμών τους. Οι γραμματικές με λογικούς τελεστές
προκύπτουν από την προσθήκη τελεστών σύζευξης και άρνησης στις απλές ασυμφραστικές
γραμματικές. Θεωρούμε το σύνολο κανόνων τους ως ένα λογικό τύπο, ειδικότερα ένα σύστη-
μα γλωσσικών ανισώσεων, και τις εξετάζουμε από μια λογική σκοπιά. Οι σημασιολογίες που
μελετάμε προέρχονται από την περιοχή του λογικού προγραμματισμού και συγκεκριμένα από
τη σημασιολογία Kripke-Kleene και την καλά θεμελιωμένη σημασιολογία. Και στις δύο
χρησιμοποιείται η έννοια της τριαδικής γλώσσας, στην οποία μια συμβολοσειρά μπορεί να
ανήκει, να μην ανήκει ή το αν ανήκει να είναι αόριστο. Η πρώτη προσέγγιση των σημασιο-
λογιών έχει μοντελοθεωρητικό χαρακτήρα, δηλαδή στηρίζεται σε ερμηνείες των μεταβλητών
μιας γραμματικής ως γλώσσες και στην επιλογή της τομής των ερμηνειών που ικανοποιούν
τους κανόνες της γραμματικής. Στη συνέχεια προσεγγίζουμε τις σημασιολογίες μέσω σταθε-
ρών σημείων συναρτήσεων. Εδώ σχετίζουμε γραμματικές με συναρτήσεις από ερμηνείες σε
ερμηνείες και χρησιμοποιούμε τα ελάχιστα σταθερά σημεία αυτών των συναρτήσεων, τα
οποία χαρακτηρίζουμε ως όρια κάποιων ακολουθιών προσεγγίσεων. Το τρίτο είδος σημασιο-
λογικών προσεγγίσεων στηρίζεται σε συνδυαστικά παιχνίδια δύο παικτών. Έχουμε δηλαδή
παιχνίδια όπου δύο παίκτες επιχειρηματολογούν με βάση τους κανόνες μιας γραμματικής για
το αν ανήκουν διάφορες συμβολοσειρές στις γλώσσες που αντιπροσωπεύουν διάφοροι όροι
και οι σημασιολογίες χαρακτηρίζονται μέσω της τιμής παιχνιδιών που σχετίζονται με γραμμα-
τικές. Παρουσιάζουμε μια άπειρη εκδοχή αυτών των παιχνιδιών (προϋπάρχουσα για την καλά
θεμελιωμένη σημασιολογία) και εισάγουμε μια ισοδύναμη πεπερασμένη εκδοχή τους. Τέλος,
προτείνουμε κάποιες σημασιολογικές προσεγγίσεις που βασίζονται σε συστήματα αναγραφής
όρων. Στο πρώτο είδος αναγραφής, αποφασίζεται το κατά πόσο ανήκουν διάφορες συμβολο-
σειρές σε διάφορες γλώσσες. Ο αιτιοκρατικός χαρακτήρας του (η χρησιμοποιούμενη σχέση
αναγραφής έχει ως πυρήνα μια συνάρτηση) μας οδηγεί σε ένα γενικό, αναδρομικό, “από πάνω
προς τα κάτω” αλγόριθμο απόφασης, παρόμοιο με τον αλγόριθμο του Unger για τις απλές
ασυμφραστικές γραμματικές, και σε δύο τροποποιήσεις του, εκ των οποίων η μία μειώνει τον
απαιτούμενο χρόνο και η άλλη τον απαιτούμενο χώρο. Στο δεύτερο είδος αναγραφής,
αναγνωρίζονται μη αιτιοκρατικά συμβολοσειρές που ανήκουν ή δεν ανήκουν σε διάφορες
γλώσσες. Από αυτό καταλήγουμε σε ένα ακόμη είδος αναγραφής όπου παράγονται συμβολο-
σειρές που ανήκουν ή δεν ανήκουν σε διάφορες γλώσσες, περίπου όπως στον κλασικό χαρα-
κτηρισμό της σημασιολογίας των απλών ασυμφραστικών γραμματικών.
In this thesis we study two kinds of semantics for Boolean grammars through different characterizations. Boolean grammars arise from adding conjunction and negation operators to simple context-free grammars. We see their set of rules as a logical formula, a system of language inequations in particular, and we examine them from a logical point of view. The kinds of semantics we study come from the area of logic programming, specifically from the Kripke-Kleene semantics and the well-founded one. Both of them use the notion of ternary languages, where a string can belong, not belong or have undefined membership. Our first approach to the semantics is of a model-theoretic nature. It relies on interpretations of the variables of a grammar as languages and on choosing the intersection of the interpretations that satisfy the rules. Next, we approach the semantics through fixpoints of functions. Now we relate grammars to functions from interpretations to interpretations and use the least fixpoints of these functions, which we characterize as limits of certain sequences of approximations. The third kind of semantic approaches used is based on combinatorial two-player games. Here we have games where two players argue, using the rules of a grammar, whether some strings belong to the languages that some terms stand for and the semantics is characterized using the values of games related to grammars. We show an infinite version of these games (already existing for the well-founded semantics) and we introduce an equivalent finite version of them. Finally, we propose some semantic approaches based on term-rewriting systems. In the first kind of rewriting, the membership of several strings in several languages is decided. Its deterministic character (the rewriting relation used has a function as a kernel) leads us to a general, recursive, “top-down” decision algorithm, similar to Unger's algorithm for simple context-free grammars, and to two modifications of it, one reducing the time needed and one reducing the space needed. In the second kind of rewriting, strings that belong or do not belong to several laguages are recognized nondeterministically. From this kind we conclude in one more kind of rewriting, where strings that belong or do not belong to several laguages are generated, pretty much like what happens in the classical characterization of the semantics of simple context-free grammars.
In this thesis we study two kinds of semantics for Boolean grammars through different characterizations. Boolean grammars arise from adding conjunction and negation operators to simple context-free grammars. We see their set of rules as a logical formula, a system of language inequations in particular, and we examine them from a logical point of view. The kinds of semantics we study come from the area of logic programming, specifically from the Kripke-Kleene semantics and the well-founded one. Both of them use the notion of ternary languages, where a string can belong, not belong or have undefined membership. Our first approach to the semantics is of a model-theoretic nature. It relies on interpretations of the variables of a grammar as languages and on choosing the intersection of the interpretations that satisfy the rules. Next, we approach the semantics through fixpoints of functions. Now we relate grammars to functions from interpretations to interpretations and use the least fixpoints of these functions, which we characterize as limits of certain sequences of approximations. The third kind of semantic approaches used is based on combinatorial two-player games. Here we have games where two players argue, using the rules of a grammar, whether some strings belong to the languages that some terms stand for and the semantics is characterized using the values of games related to grammars. We show an infinite version of these games (already existing for the well-founded semantics) and we introduce an equivalent finite version of them. Finally, we propose some semantic approaches based on term-rewriting systems. In the first kind of rewriting, the membership of several strings in several languages is decided. Its deterministic character (the rewriting relation used has a function as a kernel) leads us to a general, recursive, “top-down” decision algorithm, similar to Unger's algorithm for simple context-free grammars, and to two modifications of it, one reducing the time needed and one reducing the space needed. In the second kind of rewriting, strings that belong or do not belong to several laguages are recognized nondeterministically. From this kind we conclude in one more kind of rewriting, where strings that belong or do not belong to several laguages are generated, pretty much like what happens in the classical characterization of the semantics of simple context-free grammars.
Περιγραφή
Λέξεις-κλειδιά
Σημασιολογία, Semantics
Θεματική κατηγορία
Σημασιολογία, Γραμματική -- Επεξεργασία δεδομένων
Παραπομπή
Σύνδεσμος
Γλώσσα
el
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Νομικός, Χρήστος
Εξεταστική επιτροπή
Νομικός, Χρήστος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 115-117
Ονόματα συντελεστών
Αριθμός σελίδων
125 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: Attribution-NonCommercial-NoDerivs 3.0 United States