7738996303

Spis treści

1    Słowa skończone    5

1.1    Wstęp................................................. 5

1.2    Twierdzenie Biichiego ........................................ 6

2    Słowa nieskończone    11

2.1    Twierdzenie Biichiego ........................................ 11

2.2    Dowód twierdzenia Biichiego .................................... 12

2.3    Dopełnienie dla NBA......................................... 13

3    Interpretacje    19

4    Determinizacja    21

4.1    Podejście bezpośrednie........................................ 21

4.2    Drzewa Safry............................................. 22

4.3    Symulacja............................................... 22

4.4    Automat................................................ 23

4.5    Twierdzenie odwrotne........................................ 25

4.6    Alternatywna konstrukcja...................................... 25

4.7    Wnioski................................................ 27

5    Języki regularne słów skończonych    29

5.1    Języki regularne słów skończonych a logika pierwszego rzędu (FO) ............... 29

6    Alternacja    35

6.1    Alternacja na słowach skończonych................................. 35

6.2    Alternacja na słowach nieskończonych............................... 39

6.3    Determinacja gier nieskończonych a automaty alternujące.................... 41

7    Drzewa    51

7.1    Drzewa skończone .......................................... 51

7.2    Drzewa nieskończone......................................... 56

8    Inne teorie rozstrzygalne    65

9    Rozwiązania zadań    69

3