Θεωρία Τυπικών Γλωσσών
Αντικείμενο
Αλφάβητα. Άπειρες λέξεις και ω-γλώσσες. Αυτόματα σε άπειρες λέξεις: Büchi και Muller συνθήκες αναγνωρισιμότητας. ω-Αναγνωρίσιμες γλώσσες. Ιδιότητες ω-αναγνωρίσιμων γλωσσών. Το πρόβλημα της συμπληρωματικής μιας ω-αναγνωρίσιμης γλώσσας. Μοναδιακή λογική δεύτερης τάξης. Ισοδυναμία προτάσεων μοναδιακής λογικής δεύτερης τάξης και αυτομάτων σε άπειρες λέξεις. Εφαρμογή αυτομάτων σε άπειρες λέξεις στον έλεγχο μοντέλων.
Βιβλιογραφία
-
C. Baier, J.-P. Katoen, Principles in model checking, MIT Press, 2008.
-
B. Khoussainov, A. Nerode, Automata Theory and its Applications, Birkhäuser Boston, 2001.
-
W. Thomas, Automata on infinite objects, in: Handbook of Theoretical Computer Science, vol. B (J. v. Leeuwen, ed.), Elsevier Science Publishers, Amsterdam 1990, pp. 135-191.
-
W. Thomas, Languages, automata and logic, in: Handbook of Formal Languages, vol. 3 (G. Rozenberg, A. Salomaa, eds.), Springer, 1997, pp. 389-485.
-
M-H. Tsai, S. Fogarty, M.Y. Vardi, Y-K. Tsay, State of Büchi complementation, Full version of CIAA 2010 paper ,
http://www.cs.rice.edu/~vardi/papers/ciaa10rj.pdf
-
Q. Yan, Lower bounds for complementation of omega-automata via the full automata technique, Logical Methods in Computer Science 4(2005), 1-20.