Wyszukiwarka
Abstrakt
We describe an algorithm that allows the incremental addition or removal of unranked ordered trees to minimal frontier-to-root deterministic tree automaton (DTA). The algorithm takes a tree t and a minimal DTA A as input; it outputs a minimal DTA A' which accepts the language L(A) accepted by A incremented (or decremented) with the tree t. The algorithm can be used to efficiently maintain dictionaries which store large collections of trees or tree fragments.Opisujemy algorytm pozwalający na przyrostowe dodawanie bądź usuwanie drzew o nieustalonej krotności symboli etykietujących wierzchołki to minimalnego, wstępującego, deterministycznego, skończonego automatu drzewiastego (DTA). Algorytm ma na wejściu drzewo t i minimalny DTA A. Na wyjściu pojawia się automat A', który rozpoznaje język L(A) automatu A rozszerzony o drzewo t. Algorytm może być użyty do wydajnej pielęgnacji słowników przechowujących duże zbiory drzew lub fragmentów drzew.
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 w czasopiśmie
- Typ:
- artykuł w czasopiśmie wyróżnionym w JCR
- Opublikowano w:
-
ALGORITHMICA
nr 55,
strony 95 - 110,
ISSN: 0178-4617 - Język:
- angielski
- Rok wydania:
- 2009
- Opis bibliograficzny:
- Carrasco R., Daciuk J., Forcada M.: Incremental construction of Minimal Tree Automata [online]// ALGORITHMICA. -Vol. 55, nr. iss. 1 September (2009), s.95-110
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 116 razy
Publikacje, które mogą cię zainteresować
An implementation of deterministic tree automata minimization
- R. Carrasco,
- J. Daciuk,
- M. Forcada