Wyniki wyszukiwania dla: PRZYROSTOWE TWORZENIE MINIMALNYCH AUTOMATÓW DRZEWIASTYCH - MOST Wiedzy

Wyszukiwarka

Wyniki wyszukiwania dla: PRZYROSTOWE TWORZENIE MINIMALNYCH AUTOMATÓW DRZEWIASTYCH

Wyniki wyszukiwania dla: PRZYROSTOWE TWORZENIE MINIMALNYCH AUTOMATÓW DRZEWIASTYCH

  • Incremental and pseudo-incremental construction of pseudo-minimal automata.

    Publikacja

    - 2006

    Automaty pseudominimalne mają dla każdego słowa w języku automatu co najmniej jeden element własny (stan lub przejście), który nie jest współdzielony z żadnym innym słowem. Przedstawiamy przyrostowe i półprzyrostowe algorytmy tworzenia takich automatów.

    Pełny tekst w serwisie zewnętrznym

  • An implementation of deterministic tree automata minimization

    Publikacja

    - 2007

    Wstępujący, deterministyczny, skończony automat drzewiasty (DTA) może być używany jako struktura danych do przechowywania zbiorów nieuporządkowanych drzew bez narzuconej liczby poddrzew. Takie automaty są zwykle rzadsze niż automaty działające na napisach i dlatego należy zwrócić szczególną uwagę na ich wydajną minimalizację. W dostępnej literaturze jest jednak ciężko znaleźć proste i szczegółowe opisy procedury minimalizacji....

  • Comparison of construction algorithms for minimal, acyclic, deterministicfinite state automata from sets of strings.

    Artykuł porównuje różne metody tworzenia minimalnych, acyklicznych, deterministycznych automatów skończonych ze zbiorów słów. Wdrożone i porównane zostały metody przyrostowe, prawie przyrostowe i nieprzyrostowe.

  • Incremental construction of finite-state automata

    Publikacja

    - 2013

    Rozdział przedstawia algorytmy przyrostowego i półprzyrostowego tworzenia minimalnych deterministycznych automatów skończonych.

    Pełny tekst w serwisie zewnętrznym

  • Incremental and Semi-Incremental Construction of Pseudo-Minimal Automata

    Publikacja

    - 2005

    Przedstawione zostają modyfikacje trzech algorytmów przyrostowego i półprzyrostowego tworzenia automatów minimalnych w taki sposób, aby tworzyły automaty pseudominimalne. Istniejący od dawna algorytm Revuza tworzy takie automaty szybciej i zużywając mniej pamięci, ale wymaga kłopotliwego sortowania. Nie nadaje się też do dodawania nowych słów do automatu - ważnej czynności w realizacji dynamicznej doskonałej funkcji mieszającej....

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

    Publikacja

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

  • Comments on ''Incremental construction and maintenance of minimal finite-state automata'' by Rafael C. Carrasco and Mikel L. Forcada.

    Publikacja

    - 2004

    W opublikowanym niedawno artykule (czerwiec 2002) Rafael Carrasco i Mikel Forcada przedstawili dwa algorytmy: jeden dotyczący przyrostowego dodawania łańcuchów znaków do języka minimalnego, deterministycznego, cyklicznego automatu skończonego, drugi dotyczący przyrostowego usuwania łańcuchów znaków z automatu. Pierwszy algorytm jest uogólnieniem ,,algorytmu dla danych nieuporządkowanych'' - drugiego z dwóch przyrostowych algorytmów...

  • Smaller Representation of Finite State Automata

    Publikacja

    This paper is a follow-up to Jan Daciuk's experiments on space-effcient finite state automata representation that can be used directly for traversals in main memory. We investigate several techniques of reducing memory footprint of minimal automata, mainly exploiting the fact that transition labels and transition pointer offset values are not evenly distributed and so are suitable for compression. We achieve a gain of around 20-30%...

    Pełny tekst w serwisie zewnętrznym

  • Smaller representation of finite state automata

    Publikacja

    This paper is a follow-up to Jan Daciuk's experiments on space-efficient finite state automata representation that can be used directly for traversals in main memory (Daciuk, 2000)[4]. We investigate several techniques for reducing memory footprint of minimal automata, mainly exploiting the fact that transition labels and transition pointer offset values are not evenly distributed and so are suitable for compression. We achieve...

    Pełny tekst w serwisie zewnętrznym

  • Incremental construction of Minimal Tree Automata [online]

    Publikacja

    - ALGORITHMICA - 2009

    We describe an algorithm that allows the incremental addition or removal of unranked ordered trees to minimal frontier-to-root deterministic tree automaton (DTA). The algorithm takes a tree t and a minimal DTA A as input; it outputs a minimal DTA A' which accepts the language L(A) accepted by A incremented (or decremented) with the tree t. The algorithm can be used to efficiently maintain dictionaries which store large collections...

    Pełny tekst w serwisie zewnętrznym

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

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

    Pełny tekst w serwisie zewnętrznym