4130649338

Streszczenie

W pracy opisana jest struktura algebraiczna, za pomocą której można reprezentować regularne języki drzew nieurangowanych. Pokazane jest również kilka typów automatów rozpoznających te obiekty. Następnie porównane są rozmiary wszystkich podanych reprezentacji. Głównym wynikiem pracy jest fakt, ż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.

Słowa kluczowe

drzewa nieurangowane, języki regularne, UTA, algebry lasów, rozmiar reprezentacji

Dziedzina pracy (kody wg programu Socrates-Erasmus)

11.3 Informatyka

Klasyfikacja tematyczna

F. Theory of Computation

F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES F.4.3 Formal Languages

Tytuł pracy w języku angielskim:

Comparing Sizes of Representations of Regular Languages of Unranked Trees