Αυτόματα σε ημιδακτύλιους
Αντικείμενο
Ημιδακτύλιοι. Αυτόματα με βάρη σε ημιδακτύλιους. Αναγνωρίσιμες σειρές. Ιδιότητες αναγνωρίσιμων σειρών. Το πρόβλημα της προσδιοστότητας των αυτομάτων με βάρη. Προβλήματα αποφασισιμότητας. Εφαρμογές: Ασαφείς γλώσσες. Ψηφιακή συμπίεση εικόνας.
Βιβλιογραφία
-
M. Droste, W. Kuich, and H. Vogler, eds., Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, Springer, 2009.
-
-
W. Kuich, Semirings and formal power series: Their relevance to formal languages and automata theory, in: Handbook of of Formal Languages, volume 1, Chapter 9, Springer, Berlin, pages 609-667.
-
W. Kuich A. Salomaa, Semirings, Automata, Languages, EATCS Monographs in Theoretical Computer Science, Springer, 1986.
-
J. Sakarovitch, Elements of Automata Theory, Cambridge, 2009.
-
A. Salomaa, M. Soittola, Automata-Theoretic Aspects of Formal Power Series, Springer, Berlin, 1978.
-
J. Berstel, Ch. Reutenauer, Rational Series and Their Languages, EATCS Monographs in Theoretical Computer Science, Springer, 1988.
Σημειώσεις