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
- Rafael Carrasco,
- dr hab. inż. Jan Daciuk link otwiera się w nowej karcie ,
- Mikel Forcada
Informacje dodatkowe
- Kategoria
- Publikacja monograficzna
- Typ
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Język
- angielski
- Rok wydania
- 2007
Źródło danych: MOSTWiedzy.pl - publikacja "An implementation of deterministic tree automata minimization" link otwiera się w nowej karcie
