Perfect hashing tree automata

Jan Daciuk

Perfect hashing tree automata

Abstract

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.

Author (1)

Jan Daciuk dr hab. inż.

Cite as

Full text

full text is not available in portal

full content of the article see on external site open in new tab

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:: Finite-State Methods and Natural Language Processing strony 97 - 106
Language:: English
Publication year:: 2008
Bibliographic description:: Daciuk J.: Perfect hashing tree automata// Finite-State Methods and Natural Language Processing/ ed. eds: T. Hanneforth, K.-M. Würzner. Potsdam: Potsdam University Press, 2008, s.97-106
Verified by:: Gdańsk University of Technology