An implementation of deterministic tree automata minimization

Rafael Carrasco; Jan Daciuk; Mikel Forcada

An implementation of deterministic tree automata minimization

Abstrakt

Wstępujący, deterministyczny, skończony automat drzewiasty (DTA) może być używany jako struktura danych do przechowywania zbiorów nieuporządkowanych drzew bez narzuconej liczby poddrzew. Takie automaty są zwykle rzadsze niż automaty działające na napisach i dlatego należy zwrócić szczególną uwagę na ich wydajną minimalizację. W dostępnej literaturze jest jednak ciężko znaleźć proste i szczegółowe opisy procedury minimalizacji. Opisujemy tutaj prostą realizację standardowego algorytmu minimalizacji, który wykonuje się w czasie o(|A|^2), gdzie |A| oznacza rozmiar automatu.

Autorzy (3)

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja monograficzna
Typ:: rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
Tytuł wydania:: w: Implementation and Application of Automata strony 122 - 129
Język:: angielski
Rok wydania:: 2007
Opis bibliograficzny:: Carrasco R., Daciuk J., Forcada M.: An implementation of deterministic tree automata minimization// w: Implementation and Application of Automata/ ed. eds: J. Holub, J. Ždárek. Berlin Heidelberg: Springer-Verlag, 2007, s.122-129
Weryfikacja:: Politechnika Gdańska