see the original item page
in the repository's web site and access all digital files if the item*
share




2008 (EN)
Αυτόματα δένδρων με βάρη και discounting
Weighted tree automata with discounting

Μανδραλή, Ελένη Γεωργίου

Ορίζουμε top-down και bottom-up αυτόματα δένδρων με βάρη και discounting σε αντιμεταθετικούς ημιδακτυλίους. Αποδεικνύουμε ότι τα δύο παραπάνω μοντέλα αναγνωρίζουν την ίδια κλάση σειρών δένδρων. Για την κλάση αυτή αποδεικνύουμε ένα Θεώρημα τύπου Kleene, καθώς επίσης δίνουμε τον λογικό χαρακτηρισμό της. Τέλος, ορίζουμε Muller αυτόματα δένδρων με βάρη και discounting στους max-plus και min-plus ημιδακτυλίους και δείχνουμε πως η κλάση των σειρών άπειρων δένδρων που αναγνωρίζονται από αυτά τα μοντέλα, μπορεί να περιγραφεί από δύο βασικά είδη προτάσεων της μοναδιαίας λογικής δεύτερης τάξης με βάρη και discounting σε άπειρα δένδρα.
We consider weighted top-down tree automata and weighted bottom-up tree automata with discounting over commutative semirings, and we show that the two models accept the same class of formal tree series. For this class of tree series we establish a Kleene theorem and an MSO logical characterization. Then, we introduce weighted Muller tree automata with discounting over the max-plus and the min-plus semirings, and we show their expressive equivalence with two fragments of weighted MSO sentences.

info:eu-repo/semantics/masterThesis
Postgraduate Thesis / Μεταπτυχιακή Εργασία

Αυτόματα δένδρων με βάρη και discounting
Ρητές πράξεις σε σειρές δένδρων και discounting
Μοναδιαία λογική δεύτερης τάξης σε πεπερασμένα κι άπειρα δένδρα
Discounting
Semirings
Weighted tree automata with discounting
Muller δενδροαυτόματα με βάρη και discounting
Weighted MSO logic over finite and infinite trees
Weighted Muller tree automata with discounting
Ημιδακτύλιοι
Rational tree series operation with discounting

Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (EL)
Aristotle University of Thessaloniki (EN)

Greek
English

2008
2009-10-08T06:41:44Z


Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, Σχολή Θετικών Επιστημών, Τμήμα Μαθηματικών

This record is part of 'IKEE', the Institutional Repository of Aristotle University of Thessaloniki's Library and Information Centre found at http://ikee.lib.auth.gr. Unless otherwise stated above, the record metadata were created by and belong to Aristotle University of Thessaloniki Library, Greece and are made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). Unless otherwise stated in the record, the content and copyright of files and fulltext documents belong to their respective authors. Out-of-copyright content that was digitized, converted, processed, modified, etc by AUTh Library, is made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). You are kindly requested to make a reference to AUTh Library and the URL of the record containing the resource whenever you make use of this material.
info:eu-repo/semantics/openAccess



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)