Przegląd tego, co się działo w teorii automatow skończonych od lat 50-tych (czyli tego, co się nie zmieściło na wykładzie z językow formalnych).
Języki formalne i złożoność obliczeniowa
# Automaty na słowach skończonych
#* przypomnienie definicji i własności
#* zastosowanie do rozstrzygalności arytmetyki Presburgera
#* automaty alternujące
# Automaty na słowach nieskończonych (automaty Buchiego)
#* definicja i własności
#* zastosowania:
#** weryfikacja - sprawdzanie modelu dla logiki LTL
#** rozstrzygalność logiki S1S
# Automaty na drzewach skończonych
# Automaty na drzewach nieskończonych
# Automaty czasowe
Wolfgang Thomas, Automata on Infinite Objects, Handbook of Theoretical Computer Science, volume B,1990
Hubert Comon, Max Dauchet, Remi Gilleron, Florent Jacquemard, Denis Lugiez, Sophie Tison and Marc Tommasi, Tree Automata Techniques and Applications, www.grappa.univ-lille3.fr/tata