RECOGNIZABILITY AND REPRESENTABILITY OF FORMAL TREE POWER SERIES

 
This item is provided by the institution :

Repository :
National Archive of PhD Theses
see the original item page
in the repository's web site and access all digital files if the item*
share



PhD thesis (EN)

1988 (EN)

ΑΝΑΓΝΩΡΙΣΙΜΟΤΗΤΑ ΚΑΙ ΑΝΑΠΑΡΑΣΤΑΣΙΜΟΤΗΤΑ ΔΕΝΔΡΟΣΕΙΡΩΝ
RECOGNIZABILITY AND REPRESENTABILITY OF FORMAL TREE POWER SERIES

Αλεξανδράκης, Αθανάσιος

WE PRESENT A THEORY OF RECOGNIZABLE FORMAL TREE POWER SERIES USING THE NOTION OF SYNTACTIC IK-Σ-ALGEBRA OF A TREE SERIES. THE RECOGNIZABILITY OF SUCH A SERIESIS RELATED WITH THE EXISTENCE OF A REALIZATION FOR THIS SERIES. WE PROVE THAT A TREE SERIES IS RECOGNIZABLE IF AND ONLY IF ITS SYNTACTIC ΙΚ-Σ-ALGEBRA IS OF FINITE TYPE. NEXT WE CHARACTERIZE RECOGNIZABLE FORMAL SERIES ON TREES BY MEANS OF MATRIX REPRESENTATIONS. FURTHERMORE, WE PROVE THAT THE IMAGE OF SUCH A REPRESENTATION WITH MINIMUM DIMENSION IS ISOMORPHIC TO SYNTACTIC ΙΚ-Σ-ALGEBRA OF THE INDUCED SERIES. FINALLY, WE SHOW THAT TWO MINIMAL MATRIX REPRESENTATIONS OF THESAME SERIES, ARE "SIMILAR". ALSO, USING REGULAR TREE GRAMMARS WEIGHTED OVER A SEMIRING, WE ESTABLISH KLEENE'S THEOREM IN THE CONTEST OF FORMAL TREE POWER SERIES.
ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΜΙΑ ΘΕΩΡΙΑ ΑΝΑΓΝΩΡΙΣΙΜΩΝ ΤΥΠΙΚΩΝ ΔΕΝΔΡΟΣΕΙΡΩΝ ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΤΗΝΕΝΝΟΙΑ ΤΗΣ ΣΥΝΤΑΚΤΙΚΗΣ ΙΚ-Σ-ΑΛΓΕΒΡΑΣ ΜΙΑΣ ΣΧΗΜΑΤΙΚΗΣ ΔΕΝΔΡΟΣΕΙΡΑΣ. Η ΑΝΑΓΝΩΡΙΣΙΜΟΤΗΤΑ ΜΙΑΣ ΔΕΝΔΡΟΣΕΙΡΑΣ ΣΧΕΤΙΖΕΤΑΙ ΜΕ ΤΗΝ ΥΠΑΡΞΗ ΜΙΑΣ ΠΡΑΓΜΑΤΟΠΟΙΗΣΗΣ ΤΗΣ. ΑΠΟΔΕΙΚΝΥΟΥΜΕ ΟΤΙ ΜΙΑ ΔΕΝΔΡΟΣΕΙΡΑ ΕΙΝΑΙ ΑΝΑΓΝΩΡΙΣΙΜΗ ΑΝ ΚΑΙ ΜΟΝΟΝ ΑΝ Η ΣΥΝΤΑΚΤΙΚΗΤΗΣ ΙΚ-Σ-ΑΛΓΕΒΡΑ ΕΙΝΑΙ ΠΕΠΕΡΑΣΜΕΝΗΣ ΓΕΝΕΣΗΣ. ΚΑΤΟΠΙΝ ΧΑΡΑΚΤΗΡΙΖΟΥΜΕ ΤΙΣ ΑΝΑΓΝΩΡΙΣΙΜΕΣ ΤΥΠΙΚΕΣ ΔΕΝΔΡΟΣΕΙΡΕΣ ΜΕ ΜΕΣΑ ΤΩΝ ΑΝΑΠΑΡΑΣΤΑΣΕΩΝ ΠΙΝΑΚΩΝ. ΕΠΙΠΛΕΟΝ, ΑΠΟΔΕΙΚΝΥΟΥΜΕ ΟΤΙ Η ΕΙΚΟΝΑ ΜΙΑΣ ΤΕΤΟΙΑΣ ΑΝΑΠΑΡΑΣΤΑΣΗΣ ΜΕ ΕΛΑΧΙΣΤΗ ΔΙΑΣΤΑΣΗ ΕΙΝΑΙ ΙΣΟΜΟΡΦΗ ΜΕ ΤΗ ΣΥΝΤΑΚΤΙΚΗ ΙΚ-Σ-ΑΛΓΕΒΡΑ ΤΗΣ ΕΠΑΓΟΜΕΝΗΣ ΔΕΝΔΡΟΣΕΙΡΑΣ. ΤΕΛΙΚΑ, ΔΕΙΧΝΟΥΜΕ ΟΤΙ ΔΥΟ ΕΛΑΧΙΣΤΕΣ ΑΝΑΠΑΡΑΣΤΑΣΕΙΣ ΠΙΝΑΚΩΝ ΤΗΣ ΙΔΙΑΣ ΣΕΙΡΑΣ ΕΙΝΑΙ "ΟΜΟΙΕΣ". ΕΠΙΣΗΣ, ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΟΜΑΛΕΣ ΔΕΝΔΡΟΓΡΑΜΜΑΤΙΚΕΣ ΜΕ ΒΑΡΗ ΠΑΝΩ Σ'ΕΝΑ ΗΜΙΔΑΚΤΥΛΙΟ, ΑΠΟΚΑΘΙΣΤΟΥΜΕ ΤΟ ΘΕΩΡΗΜΑ ΤΟΥ KLEENE ΓΙΑ ΤΙΣ ΤΥΠΙΚΕΣ ΔΕΝΔΡΟΣΕΙΡΕΣ.

PhD Thesis

REGULAR TREE GRAMMAR WEIGHTED OVER A SEMIRING
ΠΡΑΓΜΑΤΟΠΟΙΗΣΗ ΔΕΝΔΡΟΣΕΙΡΑΣ
Μαθηματικά
Mathematics
REPRESENTABLE TREE SERIES
REALIZATION OF A TREE SERIES
Φυσικές Επιστήμες
MATRIX REPRESENTATION
ΘΕΩΡΗΜΑ ΤΟΥ KLEENE
RECOGNIZABLE FORMAL TREE POWER SERIES
ΣΥΝΤΑΚΤΙΚΗ Κ-Σ-ΑΛΓΕΒΡΑ
ΑΝΑΓΝΩΡΙΣΙΜΗ ΤΥΠΙΚΗ ΔΕΝΔΡΟΣΕΙΡΑ
ΟΜΑΛΗ ΔΕΝΔΡΟΓΡΑΜΜΑΤΙΚΗ ΜΕ ΒΑΡΗ
KLEENE'S THEOREM
Natural Sciences
SYNTACTIC IK-Σ-ALGEBRA
ΑΝΑΠΑΡΑΣΤΑΣΗ ΠΙΝΑΚΩΝ
ΑΝΑΠΑΡΑΣΤΑΣΙΜΗ ΔΕΝΔΡΟΣΕΙΡΑ


Greek

1988


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




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