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

Abstract

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 ΓΙΑ ΤΙΣ ΤΥΠΙΚΕΣ ΔΕΝΔΡΟΣΕΙΡΕΣ.