An implementation of deterministic tree automata minimization

Rafael Carrasco; Jan Daciuk; Mikel Forcada

An implementation of deterministic tree automata minimization

Abstract

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.

Authors (3)

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:: Monographic publication
Type:: rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
Title of issue:: w: Implementation and Application of Automata strony 122 - 129
Language:: English
Publication year:: 2007
Bibliographic description:: 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
Verified by:: Gdańsk University of Technology