Abstrakt
We describe a technique that maps unranked trees to their hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to techniques implemented with minimal tree automata, our procedure builds a pseudo-minimal DTA. Pseudo-minimal automata are larger than the minimal ones but in turn the mapping can be arbitrary, so it can be determined prior to the automaton construction. We also provide procedures to build incrementally the pseudo-minimal DTA and the associated hash codes.Opisujemy technikę odwzorowującą drzewa w wartości funkcji mieszającej używając wstępujących, deterministycznych automatów drzewiastych. W przeciwieństwie do technik opartych o minimalne automaty drzewiaste, nasza metoda tworzy automaty pseudominimalne. Automaty pseudominimalne są większe niż minimalne, ale odwzorowanie może być dowolne, a więc może być znane przed utworzeniem automatu. Dostarczamy również procedurę budowy automatu pseudominimalnego z funkcją mieszającą.
Autorzy (2)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Tytuł wydania:
- Intelligent Information Systems XVI : proceedings of the International IIS`08 Conference held in Zakopane, Poland, June 16-18, 2008 strony 229 - 238
- Język:
- angielski
- Rok wydania:
- 2008
- Opis bibliograficzny:
- Daciuk J., Carrasco R.: Perfect hashing with pseudo-minimal bottom-up deterministic tree automata// Intelligent Information Systems XVI : proceedings of the International IIS`08 Conference held in Zakopane, Poland, June 16-18, 2008/ ed. eds. M.A. Kłopotek [et al]. Warszawa: Academic Publishing House EXIT, 2008, s.229-238
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 111 razy
Publikacje, które mogą cię zainteresować
Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata
- J. Daciuk,
- D. Maurel,
- A. Savary
Incremental and pseudo-incremental construction of pseudo-minimal automata.
- J. Daciuk,
- D. Maurel,
- A. Savary
An implementation of deterministic tree automata minimization
- R. Carrasco,
- J. Daciuk,
- M. Forcada