Kolloquium des Graduiertenkolleg Wissensrepräsentation

Dr. George Rahonis

Weighted automata over finite and infinite words



We recall basic notions on finite automata. Then we turn to weighted automata which are classical automata whose transitions, initial and terminal states are equipped with weights from a semiring. These models are widely used in speech-to-text processing [16,17,18] and digital image compression [2,3,4,10,11,15]. For the theory of weighted automata see [1,12,13]. In the second part of this lecture, we deal with automata consuming infinite words and especially with Buchi and Muller models. These automata constitute tools in model checking techniques [8,9,14]. We refer to properties of their accepted languages as well as to the determinization problem. Finally, we expose the recently appeared weighted automata over infinite words with Buchi and Muller acceptance condition [5,6,7].

References

1) J. Berstel, C. Reutenauer, Rational Series and Their Languages. EATCS Monographs in Theoretical Computer Science, vol. 12, Springer-Verlag, 1998.
2) K. Culik II, J. Kari, Image compression using weighted finite automata, Computer and Graphics, 58(1993) 303-313.
3) K. Culik II, J. Kari, Weighted finite transducers in image processing, Discrete Applied Mathematics 58(1995) 223-237.
4) K. Culik II, J. Kari, Computational fractal geometry with WFA, Acta Informatica 34(1997) 151-166.
5) M. Droste, G. Rahonis, Weighted automata and weighted logics on infinite words, in: Proceedings of DLT' 06, LNCS 4036(2006) 49-58.
6) Z. Esik, W. Kuich, A semiring-semimodule generalization of omega-regular languages I. Special issue on "Weighted automata" (M. Droste, H. Vogler, eds.) Journal of Automata Languages and Combinatorics 10(2005) 203-242.
7) Z. Esik, W. Kuich, A semiring-semimodule generalization of omega-regular languages II. Special issue on "Weighted automata" (M. Droste, H. Vogler, eds.) Journal of Automata Languages and Combinatorics 10(2005) 243-264.
8) P. Gastin, D. Oddoux, Fast LTL to Buchi automata translation, in: Proceedings of CAV'01, LNCS 2102(2001) 53-65.
9) R. Gerth, D. Peled, M. Vardi, P. Wolper, Simple on-the-fly automatic verification of linear temporal logic, in:Proceedings of the 15th IFIG, Chapman and Hall, Ltd, 1996, pp. 3-18.
10) U. Hafner, Low-Bit Rate Image and Video Coding with Weighted Finite Automata, PhD thesis, Universitat Wurzburg, Germany, 1999.
11) F. katritzke, Refinements of data compression using weighted finite automata, PhD thesis, Universitat Siegen, Germany, 2001.
12) W. Kuich, A. Salomaa, Semirings, Automata, Languages. EATCS Monographs on Theoretical Computer SCience vol. 12, Springer- Verlag, 1988.
13) A. Salomaa, M. Soittola, Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs in Computer Science, Springer- Verlag, 1978.
14) P. Wolper, Constructing automata from temporal logic formulas: a tutorial, in: Lectures on formal methods and performance analysis: first EEF/Euro summer cschool on trends in computer science. Springer-Verlag, New York, Inc., 2002, pp. 261-277.
15) J. Zang, B. Litow, O. de Vel, Similarity enrichment in image compression through weighted finite automata, in:COCOON'00, LNCS 1858(2000) 447-456.
16) http://www.research.att.com/~fsmtools/fsm/
17) http://www.research.att.com/~fsmtools/dcd/
18) http://cs.nyu.edu/~mohri/



Alle Interessenten sind herzlich eingeladen.