Αυτόματα σε ημιδακτύλιους

Αντικείμενο

Ημιδακτύλιοι. Αυτόματα με βάρη σε ημιδακτύλιους. Αναγνωρίσιμες σειρές. Ιδιότητες αναγνωρίσιμων σειρών. Το πρόβλημα της προσδιοστότητας των αυτομάτων με βάρη. Προβλήματα αποφασισιμότητας. Εφαρμογές: Ασαφείς γλώσσες. Ψηφιακή συμπίεση εικόνας.

 

Βιβλιογραφία

• M. Droste, W. Kuich, and H. Vogler, eds., Handbook of Weighted Automata, EATCS Monographs in Theoretical Computer Science, Springer, 2009.

• Z. Ésik, W. Kuich, Modern Automata Theory, http://www.dmg.tuwien.ac.at/kuich/mat.ps

• 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.

Σημειώσεις