Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/30263Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Παπαδογιάννης, Παύλος | el |
| dc.date.accessioned | 2020-11-11T12:11:22Z | - |
| dc.date.available | 2020-11-11T12:11:22Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/30263 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.10151 | - |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Σημασιολογία | el |
| dc.subject | Semantics | en |
| dc.title | Σημασιολογικές προσεγγίσεις για γραμματικές με λογικούς τελεστές | el |
| dc.title | Semantic approaches for boolean grammars | en |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Σημασιολογία | - |
| heal.classification | Γραμματική -- Επεξεργασία δεδομένων | - |
| heal.dateAvailable | 2020-11-11T12:12:22Z | - |
| heal.language | el | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.publicationDate | 2016 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 115-117 | el |
| heal.abstract | Στην παρούσα διατριβή μελετώνται δύο σημασιολογίες για τις γραμματικές με λογικούς τελεστές μέσω διαφορετικών χαρακτηρισμών τους. Οι γραμματικές με λογικούς τελεστές προκύπτουν από την προσθήκη τελεστών σύζευξης και άρνησης στις απλές ασυμφραστικές γραμματικές. Θεωρούμε το σύνολο κανόνων τους ως ένα λογικό τύπο, ειδικότερα ένα σύστη- μα γλωσσικών ανισώσεων, και τις εξετάζουμε από μια λογική σκοπιά. Οι σημασιολογίες που μελετάμε προέρχονται από την περιοχή του λογικού προγραμματισμού και συγκεκριμένα από τη σημασιολογία Kripke-Kleene και την καλά θεμελιωμένη σημασιολογία. Και στις δύο χρησιμοποιείται η έννοια της τριαδικής γλώσσας, στην οποία μια συμβολοσειρά μπορεί να ανήκει, να μην ανήκει ή το αν ανήκει να είναι αόριστο. Η πρώτη προσέγγιση των σημασιο- λογιών έχει μοντελοθεωρητικό χαρακτήρα, δηλαδή στηρίζεται σε ερμηνείες των μεταβλητών μιας γραμματικής ως γλώσσες και στην επιλογή της τομής των ερμηνειών που ικανοποιούν τους κανόνες της γραμματικής. Στη συνέχεια προσεγγίζουμε τις σημασιολογίες μέσω σταθε- ρών σημείων συναρτήσεων. Εδώ σχετίζουμε γραμματικές με συναρτήσεις από ερμηνείες σε ερμηνείες και χρησιμοποιούμε τα ελάχιστα σταθερά σημεία αυτών των συναρτήσεων, τα οποία χαρακτηρίζουμε ως όρια κάποιων ακολουθιών προσεγγίσεων. Το τρίτο είδος σημασιο- λογικών προσεγγίσεων στηρίζεται σε συνδυαστικά παιχνίδια δύο παικτών. Έχουμε δηλαδή παιχνίδια όπου δύο παίκτες επιχειρηματολογούν με βάση τους κανόνες μιας γραμματικής για το αν ανήκουν διάφορες συμβολοσειρές στις γλώσσες που αντιπροσωπεύουν διάφοροι όροι και οι σημασιολογίες χαρακτηρίζονται μέσω της τιμής παιχνιδιών που σχετίζονται με γραμμα- τικές. Παρουσιάζουμε μια άπειρη εκδοχή αυτών των παιχνιδιών (προϋπάρχουσα για την καλά θεμελιωμένη σημασιολογία) και εισάγουμε μια ισοδύναμη πεπερασμένη εκδοχή τους. Τέλος, προτείνουμε κάποιες σημασιολογικές προσεγγίσεις που βασίζονται σε συστήματα αναγραφής όρων. Στο πρώτο είδος αναγραφής, αποφασίζεται το κατά πόσο ανήκουν διάφορες συμβολο- σειρές σε διάφορες γλώσσες. Ο αιτιοκρατικός χαρακτήρας του (η χρησιμοποιούμενη σχέση αναγραφής έχει ως πυρήνα μια συνάρτηση) μας οδηγεί σε ένα γενικό, αναδρομικό, “από πάνω προς τα κάτω” αλγόριθμο απόφασης, παρόμοιο με τον αλγόριθμο του Unger για τις απλές ασυμφραστικές γραμματικές, και σε δύο τροποποιήσεις του, εκ των οποίων η μία μειώνει τον απαιτούμενο χρόνο και η άλλη τον απαιτούμενο χώρο. Στο δεύτερο είδος αναγραφής, αναγνωρίζονται μη αιτιοκρατικά συμβολοσειρές που ανήκουν ή δεν ανήκουν σε διάφορες γλώσσες. Από αυτό καταλήγουμε σε ένα ακόμη είδος αναγραφής όπου παράγονται συμβολο- σειρές που ανήκουν ή δεν ανήκουν σε διάφορες γλώσσες, περίπου όπως στον κλασικό χαρα- κτηρισμό της σημασιολογίας των απλών ασυμφραστικών γραμματικών. | el |
| heal.abstract | 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. | en |
| heal.advisorName | Νομικός, Χρήστος | el |
| heal.committeeMemberName | Νομικός, Χρήστος | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 125 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΥ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΠΑΠΑΔΟΓΙΑΝΝΗΣ ΠΑΥΛΟΣ 2016.pdf | 2.83 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
