ΑΝΑΓΝΩΡΙΣΙΜΟΤΗΤΑ ΚΑΙ ΑΝΑΠΑΡΑΣΤΑΣΙΜΟΤΗΤΑ ΔΕΝΔΡΟΣΕΙΡΩΝ

Περίληψη

ΠΑΡΟΥΣΙΑΖΟΥΜΕ ΜΙΑ ΘΕΩΡΙΑ ΑΝΑΓΝΩΡΙΣΙΜΩΝ ΤΥΠΙΚΩΝ ΔΕΝΔΡΟΣΕΙΡΩΝ ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΤΗΝΕΝΝΟΙΑ ΤΗΣ ΣΥΝΤΑΚΤΙΚΗΣ ΙΚ-Σ-ΑΛΓΕΒΡΑΣ ΜΙΑΣ ΣΧΗΜΑΤΙΚΗΣ ΔΕΝΔΡΟΣΕΙΡΑΣ. Η ΑΝΑΓΝΩΡΙΣΙΜΟΤΗΤΑ ΜΙΑΣ ΔΕΝΔΡΟΣΕΙΡΑΣ ΣΧΕΤΙΖΕΤΑΙ ΜΕ ΤΗΝ ΥΠΑΡΞΗ ΜΙΑΣ ΠΡΑΓΜΑΤΟΠΟΙΗΣΗΣ ΤΗΣ. ΑΠΟΔΕΙΚΝΥΟΥΜΕ ΟΤΙ ΜΙΑ ΔΕΝΔΡΟΣΕΙΡΑ ΕΙΝΑΙ ΑΝΑΓΝΩΡΙΣΙΜΗ ΑΝ ΚΑΙ ΜΟΝΟΝ ΑΝ Η ΣΥΝΤΑΚΤΙΚΗΤΗΣ ΙΚ-Σ-ΑΛΓΕΒΡΑ ΕΙΝΑΙ ΠΕΠΕΡΑΣΜΕΝΗΣ ΓΕΝΕΣΗΣ. ΚΑΤΟΠΙΝ ΧΑΡΑΚΤΗΡΙΖΟΥΜΕ ΤΙΣ ΑΝΑΓΝΩΡΙΣΙΜΕΣ ΤΥΠΙΚΕΣ ΔΕΝΔΡΟΣΕΙΡΕΣ ΜΕ ΜΕΣΑ ΤΩΝ ΑΝΑΠΑΡΑΣΤΑΣΕΩΝ ΠΙΝΑΚΩΝ. ΕΠΙΠΛΕΟΝ, ΑΠΟΔΕΙΚΝΥΟΥΜΕ ΟΤΙ Η ΕΙΚΟΝΑ ΜΙΑΣ ΤΕΤΟΙΑΣ ΑΝΑΠΑΡΑΣΤΑΣΗΣ ΜΕ ΕΛΑΧΙΣΤΗ ΔΙΑΣΤΑΣΗ ΕΙΝΑΙ ΙΣΟΜΟΡΦΗ ΜΕ ΤΗ ΣΥΝΤΑΚΤΙΚΗ ΙΚ-Σ-ΑΛΓΕΒΡΑ ΤΗΣ ΕΠΑΓΟΜΕΝΗΣ ΔΕΝΔΡΟΣΕΙΡΑΣ. ΤΕΛΙΚΑ, ΔΕΙΧΝΟΥΜΕ ΟΤΙ ΔΥΟ ΕΛΑΧΙΣΤΕΣ ΑΝΑΠΑΡΑΣΤΑΣΕΙΣ ΠΙΝΑΚΩΝ ΤΗΣ ΙΔΙΑΣ ΣΕΙΡΑΣ ΕΙΝΑΙ "ΟΜΟΙΕΣ". ΕΠΙΣΗΣ, ΧΡΗΣΙΜΟΠΟΙΩΝΤΑΣ ΟΜΑΛΕΣ ΔΕΝΔΡΟΓΡΑΜΜΑΤΙΚΕΣ ΜΕ ΒΑΡΗ ΠΑΝΩ Σ'ΕΝΑ ΗΜΙΔΑΚΤΥΛΙΟ, ΑΠΟΚΑΘΙΣΤΟΥΜΕ ΤΟ ΘΕΩΡΗΜΑ ΤΟΥ KLEENE ΓΙΑ ΤΙΣ ΤΥΠΙΚΕΣ ΔΕΝΔΡΟΣΕΙΡΕΣ.

Περίληψη σε άλλη γλώσσα

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.
Πρέπει να είστε εγγεγραμένος χρήστης για έχετε πρόσβαση σε όλες τις υπηρεσίες του ΕΑΔΔ  Είσοδος /Εγγραφή

Όλα τα τεκμήρια στο ΕΑΔΔ προστατεύονται από πνευματικά δικαιώματα.

DOI
10.12681/eadd/0950
Διεύθυνση Handle
http://hdl.handle.net/10442/hedi/0950
Εναλλακτικός τίτλος
RECOGNIZABILITY AND REPRESENTABILITY OF FORMAL TREE POWER SERIES
Συγγραφέας
ΑΛΕΞΑΝΔΡΑΚΗΣ, ΑΘΑΝΑΣΙΟΣ
Ημερομηνία
1988
Ίδρυμα
Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (ΑΠΘ). Σχολή Θετικών Επιστημών. Τμήμα Μαθηματικών
Εξεταστική επιτροπή
ΜΠΟΖΑΠΑΛΙΔΗΣ ΣΥΜΕΩΝ
ΛΑΖΟΣ ΚΩΝΣΤΑΝΤΙΝΟΣ
ΦΥΡΑΡΙΔΗΣ ΑΝΕΣΤΗΣ
ΛΑΚΚΗΣ ΚΩΝ ΣΤΑΝΤΙΝΟΣ
ΒΑΡΔΟΥΛΑΚΗΣ ΑΝΤΩΝΙΟΣ,
Επιστημονικό πεδίο
Φυσικές Επιστήμες
Μαθηματικά
Λέξεις-κλειδιά
ΑΝΑΓΝΩΡΙΣΙΜΗ ΤΥΠΙΚΗ ΔΕΝΔΡΟΣΕΙΡΑ; ΑΝΑΠΑΡΑΣΤΑΣΗ ΠΙΝΑΚΩΝ; ΑΝΑΠΑΡΑΣΤΑΣΙΜΗ ΔΕΝΔΡΟΣΕΙΡΑ; ΘΕΩΡΗΜΑ ΤΟΥ KLEENE; ΟΜΑΛΗ ΔΕΝΔΡΟΓΡΑΜΜΑΤΙΚΗ ΜΕ ΒΑΡΗ; ΠΡΑΓΜΑΤΟΠΟΙΗΣΗ ΔΕΝΔΡΟΣΕΙΡΑΣ; ΣΥΝΤΑΚΤΙΚΗ Κ-Σ-ΑΛΓΕΒΡΑ
Χώρα
Ελλάδα
Γλώσσα
Ελληνικά