Perfect hashing tree automata
- 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.
Author details: | Jan Daciuk |
---|---|
URN: | urn:nbn:de:kobv:517-opus-27163 |
Publication type: | Conference Proceeding |
Language: | English |
Publication year: | 2008 |
Publishing institution: | Universität Potsdam |
Release date: | 2008/12/11 |
Organizational units: | Extern / Extern |
DDC classification: | 4 Sprache / 40 Sprache / 400 Sprache |
Collection(s): | Universität Potsdam / Tagungsbände/Proceedings (nicht fortlaufend) / Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 / II Regular Papers |
License (German): | Keine öffentliche Lizenz: Unter Urheberrechtsschutz |
External remark: | The complete edition of the proceedings "Finite-state methods and natural language processing : 6th International Workshop, FSMNLP 2007 ; Revised Papers" is available: URN urn:nbn:de:kobv:517-opus-23812 |