4130649340

Spis treści

Wprowadzenie....................................... 5

1.    Podstawowe pojęcia i oznaczenia ......................... 7

1.1.    Automaty skończone na słowach ......................... 7

1.2.    Drzewa nieurangowane............................... 8

2.    Automaty na drzewach nieurangowanych.................... 11

2.1.    UTA......................................... 11

2.2.    Deterministyczne automaty typu UTA...................... 12

2.3.    Automaty równoległe................................ 13

2.4.    Automaty krokowe................................. 14

2.5.    Porównanie rozmiarów różnych rodzajów    automatów.............. 14

3.    Algebry lasów...................................... 19

3.1.    Definicje....................................... 19

3.2.    Wolna algebra lasów................................ 22

3.3.    Algebry lasów a języki regularne ......................... 25

3.4.    Minimalna algebra rozpoznająca dany język................... 27

4.    Porównanie rozmiarów algebry i automatów.................. 31

4.1.    Górne ograniczenie na rozmiar algebry rozpoznającej dany język ....... 31

4.2.    Ograniczenie dolne na rozmiar algebry...................... 36

Bibliografia......................................... 39

3