An implementation of deterministic tree automata minimization - Publikacja - MOST Wiedzy

Wyszukiwarka

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.

Cytuj jako

Pełna treść

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

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

wyświetlono 11 razy

Publikacje, które mogą cię zainteresować

Meta Tagi