4130649329

Rozdział 2

Automaty na drzewach nieurangowanych

W tym rozdziale podamy definicje różnych rodzajów automatów operujących na drzewach. Pokażemy, że klasa języków rozpoznawana przez automaty każdego z tych rodzajów jest taka sama. Języki z tej klasy będziemy nazywać regularnymi językami drzew nieurangowanych.

Nazwa ta nie jest przypadkowa. Klasa ta ma bowiem analogiczne własności do klasy regularnych języków słów skończonych. Na przykład jest zamknięta na operacje boolowskie. Można też udowodnić, że języki z tej klasy to dokładnie języki rozpoznawane przez formuły logiki monadycznej drugiego rzędu¹.

Jeszcze jedną charakterystykę powyższej klasy uzasadniającą jej nazwę podamy w rozdziale 3 — będzie to skończony indeks odpowiedniej relacji Myhilla-Nerodego.

W ostatniej części niniejszego rozdziału udowodnimy kilka faktów związanych z wielkością automatów poszczególnych typów².

2.1. UTA

Definicja 2.1.1 Automat na drzewach nieurangowanych (UTA — z ang. Unranked Tree Automaton) to obiekt postaci A = (Q,T,,S,F), gdzie:

•    Q to skończony zbiór stanów (będziemy je nazywali stanami wierzchołkowymi),

•    S to skończony zbiór etykiet (alfabet),

•    5 : £ x Q —> P{Q*) jest funkcją przejścia, taką, że 6(a, q) jest regularnym językiem słów skończonych nad Q dla każdego oG £ i każdego q€ Q,

•    F C Q to zbiór stanów akceptujących.

Bieg automatu A na drzewie t to takie etykietowanie A : Dom(t) —» Q, że dla każdego wierzchołka v € Dom(t) o dzieciach v\, v2, ..., vn, słowo A(ul)A(u2)... X(vn) należy do

1

Języki regularne słów są rozpoznawane przez formuły logiki monadycznej drugiego rzędu gdzie używamy jednej relacji binarnej — relacji następnika. W przypadku drzew nieurangowanych potrzebujemy dwóch następników — pionowego i poziomego. Dokładne definicje i dowód można przeczytać w [Ne] (twierdzenie 4.11). Szerzej związki między automatami a różnymi logikami opisane są w [Th] i [Li].

2

Definicje i większość dowodów w tym rozdziale jest napisana na podstawie [MN].