ΣΥΜΒΟΛΗ ΣΤΗ ΘΕΩΡΙΑ ΤΩΝ ΣΥΝΑΡΤΗΣΕΩΝ ΔΕΝΔΡΟΥ

Abstract

ΤΟ ΚΕΝΤΡΙΚΟ ΑΠΟΤΕΛΕΣΜΑ ΤΗΣ ΔΙΑΤΡΙΒΗΣ ΕΙΝΑΙ ΤΟ ΘΕΩΡΗΜΑ ΤΟΥ TURAKAINEN ΓΙΑ ΔΕΝΔΡΑ ΠΟΥ Η ΔΙΑΤΥΠΩΣΗ ΤΟΥ ΕΧΕΙ ΩΣ ΕΞΗΣ: ΑΠΟ ΚΑΘΕ ΜΗΧΑΝΗ ΔΕΝΔΡΟΥ Α=(Q,Α,Τ) ΜΠΟΡΟΥΜΕ ΝΑ ΚΑΤΑΣΚΕΥΑΣΟΥΜΕ ΜΙΑ 1-ΜΗΧΑΝΗ ΔΕΝΔΡΟΥ P=(Q',Π,N) ΜΕ CARDQ+CARDΣΟ+3 ΕΣΩΤΕΡΙΚΕΣ ΚΑΤΑΣΤΑΣΕΙΣ ΕΤΣΙ ΩΣΤΕ ΓΙΑ ΚΑΘΕ T Ε ΤΣ-ΣΟ ΝΑ ΕΧΟΥΜΕ (ΤΥΠΟΣ). ΔΙΝΟΝΤΑΙ ΕΦΑΡΜΟΓΕΣ ΤΟΥ ΘΕΩΡΗΜΑΤΟΣ TURAKAINEN ΣΤΟ PATTERN MATCHING ΓΙΑ ΔΕΝΔΡΑ ΟΠΩΣ ΚΑΙ ΣΤΗΘΕΩΡΙΑ ΤΩΝ ΑΡΙΘΜΗΤΙΚΩΝ ΕΚΦΡΑΣΕΩΝ.

THE MAIN RESULT OF THE THESIS IS THE TURAKAINEN'S THEOREM FOR TREES THAT STATES: FROM ANY TREEMACHINE A=(Q,Α,T) WE CAN CONSTRUCT AN 1-TREEMACHINE P=(Q',Π,N) WITH CARDQ+CARDΣΟ+3 STATES, SO THAT FOR ALL TREES T Ε ΤΣ-ΣΟ IT HOLDS (TYPE). APPLICATIONS TO TREE PATTERN MATCHING AS WELL AS TO THE EVALUATION OF ARITHMETIC EXPRESSION ARE GIVEN.