4130649342

Wprowadzenie

Jest pięć powszechnie używanych charakteryzacji języków regularnych słów skończonych. Pierwsza mówi o tym, że języki regularne to te, które mogą być zdefiniowane za pomocą wyrażeń regularnych. Druga, że języki regularne rozpoznawane są przez automaty skończone. Trzecia jest w pewnym sensie pomostem łączącym drugą charakteryzację z czwartą i mówi, że języki regularne to te, dla których relacja syntaktyczna ma skończony indeks.

Czwarta, algebraiczna charakteryzacja, jest chyba najmniej znana. Okazuje się, że każdy język regularny jest przeciwobrazem pewnego zbioru przy homomorfizmie z półgrupy wolnej w pewną skończoną półgrupę. Języki nieregularne nie mają takiej skończonej reprezentacji.

Ostatnia charakteryzacja wyrasta z logiki. Języki regularne to te, które można zdefiniować za pomocą logiki monadycznej drugiego rzędu.

Okazuje się, że cztery z tych pięciu charakteryzacji są z powodzeniem stosowane w odniesieniu do regularnych języków drzew. W tej pracy będziemy się zajmowali najogólniejszym rodzajem drzew ukorzenionych — drzewami nieurangowanymi (z uporządkowanymi dziećmi wierzchołków). Zdefiniujemy automaty skończone operujące na takich drzewach. Pokażemy odpowiednią dla tych obiektów relację syntaktyczną. Skonstruujemy również strukturę algebraiczną, która może służyć do rozpoznawania takich obiektów.

Ta ostatnia została wprowadzona bardzo niedawno (przez M. Bojańczyka i I. Walukiewicza w [BW]) dlatego też jej poświęcimy najwięcej uwagi. Jednym z celów tej pracy jest właśnie umiejscowienie tego nowego pojęcia na tle istniejących wcześniej reprezentacji.

Języki regularne drzew nieurangowanych można również definiować za pomocą formuł logiki monadycznej ale tej reprezentacji nie omawiamy szerzej w niniejszej pracy.

Różne reprezentacje tych samych obiektów przyniosły w historii rozwiązanie wielu problemów decyzyjnych. Między innymi problemów definiowalności. Dobrym przykładem jest tutaj definiowalność języka słów skończonych w logice pierwszego rzędu. Okazuje się, że języki definiowalne w logice pierwszego rzędu to dokładnie języki rozpoznawane przez półgrupy z pewnej klasy definiowanej równościowo. Dokładnie są to w tym przypadku półgrupy aperiodyczne.

Kolejną korzyścią jaką daje nam wielość reprezentacji jest to, że niektóre własności języków lepiej opisują się na gruncie logiki, niektóre na gruncie algebry, a jeszcze inne na gruncie teorii automatów. I tu zaczynają być istotne konwersje między reprezentacjami.

Jeżeli na przykład mamy dany język regularny w postaci automatu, a chcemy sprawdzić jakąś jego własność, która dobrze opisuje się algebraicznie, musimy przekształcić ten automat na odpowiednią strukturę algebraiczną. W momencie gdy od pytania o rozstrzygalność pewnego problemu przechodzimy do pytania o jego złożoność to zaczyna być istotne jak zmienia się rozmiar reprezentacji przy poszczególnych konwersjach.

Z tego właśnie pytania zrodził się temat tej pracy. Podstawowy wynik jaki otrzymaliśmy to twierdzenie 4.1.1, które mówi, że rozmiar najmniejszej algebry rozpoznającej dany język regularny drzew nieurangowanych jest najwyżej pojedynczo wykładniczo większy niż rozmiar najmniejszego automatu rozpoznającego ten język.

Podamy teraz przykładową konsekwencję tego twierdzenia. Wyobraźmy sobie, że szukamy

5