We present an algorithm that computes a function that assigns consecutive integers to trees recognized by a deterministic, acyclic, finite-state, bottom-up tree automaton. Such function is called minimal perfect hashing. It can be used to identify trees recognized by the automaton. Its value may be seen as an index in some other data structures. We also present an algorithm for inverted hashing.Przedstawiamy algorytm, który oblicza funkcję przypisującą kolejne liczby całkowite do drzew rozpoznawanych przez deterministyczny, acykliczny, skończony, wstępujący automat drzewiasty. Taka funkcja nazywana jest minimalną doskonałą funkcją mieszającą. Może być użyta do identyfikacji drzew rozpoznawanych przez automat. Jej wartość może być postrzegana jako indeks w innych strukturach danych. Przedstawiamy także algorytm obliczania odwrotnej funkcji mieszającej.
Authors
Additional information
- Category
- Publikacja monograficzna
- Type
- rozdział, artykuł w książce - dziele zbiorowym /podręczniku w języku o zasięgu międzynarodowym
- Language
- angielski
- Publication year
- 2008
Source: MOSTWiedzy.pl - publication "Perfect hashing tree automata" link open in new tab
