Search results for: AUTOMATY DRZEWIASTE

• Perfect hashing with pseudo-minimal bottom-up deterministic tree automata

  Publication

  • J. Daciuk
  • R. Carrasco

  - Year 2008

  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...

• A perfect hashing incremental scheme for unranked trees using pseudo-minimal automata

  Publication

  • R. Carrasco
  • J. Daciuk

  - RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS - Year 2009

  We describe a technique that maps unranked trees to arbitrary hash codes using a bottom-up deterministic tree automaton (DTA). In contrast to other hashing techniques based on automata, our procedure builds a pseudo-minimal DTA for this purpose. A pseudo-minimal automaton may be larger than the minimal one accepting the same language but, in turn, it contains proper elements (states or transitions that are unique) for every input...

  Full text to download in external service

• Perfect hashing tree automata

  Publication

  • J. Daciuk

  - Year 2008

  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...

  Full text to download in external service