Search results for: FINITE-STATE AUTOMATA

• Smaller Representation of Finite State Automata

  Publication

  • J. Daciuk
  • D. Weiss

  - LECTURE NOTES IN COMPUTER SCIENCE - Year 2011

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

  Full text to download in external service

• Smaller representation of finite state automata

  Publication

  • J. Daciuk
  • D. Weiss

  - THEORETICAL COMPUTER SCIENCE - Year 2012

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

  Full text available to download

• Incremental construction of finite-state automata

  Publication

  • J. Daciuk

  - Year 2013

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

  Full text to download in external service

• Dynamic Perfect hashing with finite-state automata

  Publication

  • J. Daciuk
  • D. Maurel
  • A. Savary

  - Year 2005

  Minimalna doskonała funkcja mieszająca dostarcza odwzorowania zbioru n niepowtarzalnych słów w zwarty zakres n liczb całkowitych. Gdy jest realizowane za pomocą automatów skończonych, odwzorowanie wynika z porządku słów (zwykle alfabetycznego) w zbiorze. Dodanie nowych słów zmieniłoby porządek słów rozpoznawanych przez automat, zmieniając całe odwzorowanie i czyniąc je bezużytecznym w wielu dziedzinach. Dlatego nazywamy je statycznym....

• Semi- incremental construction of minimal cyclic finite state automata usingcontinuation classes.

  Publication

  • J. Daciuk

  - Year 2003

  Minimalne automaty skończone są często wybierane do przedstawiania słowników morfologicznych języka naturalnego. Wśród ich zalet znajdują się duża szybkość rozpoznawania i małe wymagania pamięciowe. Tłumaczenie opisów morfologicznych opartych o klasy kontynuacji na minimalne, cykliczne automaty skończone jest tradycyjnie dokonywane w kilku fazach, zawierających tworzenie automatu niedeterministycznego z przejściami etykietowanymi...

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

  Publication

  • J. Daciuk

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

• Natural language dictionaries implemented as finite automata

  Publication

  • J. Daciuk
  • J. Piskorski
  • S. Ristov

  - Year 2010

  Rozdział przedstawia wykorzystanie automatów skończonych jako słowników języka naturalnego. Podane są podstawy teoretyczne. Omówione są zastosowania: realizacja doskonałej funkcji mieszającej, analizy i syntezy morfologicznej, poprawiania pisowni i dopisywania znaków diakrytycznych, wydobywanie informacji. Podano algorytmy tworzenia automatów oraz omówiono sposoby reprezentacji automatów z uwzględnieniem kompresji.

  Full text to download in external service

• Finite automata for compact representation of tuple dictionaries.

  Publication

  • J. Daciuk
  • V. N. Gertjan

  - THEORETICAL COMPUTER SCIENCE - Year 2004

  Opisane zostaje uogólnienie struktury danych - słownika, zwane słownikiem n-tek. Słownik n-tek przedstawia odwzorowanie n-tek łańcuchów znaków na pewne wartości. Motywacją dla powstania tej struktury danych są praktyczne zastosowania w przetwarzaniu języka i mowy, w których obszerne słowniki n-tek używane są do przedstawiania modeli języka. Przedstawiona zostaje technika oszczędnej reprezentacji słowników n-tek. Ta technika...

  Full text available to download

• Finite automata for compact representation of language models in NLP

  Publication

  • J. Daciuk
  • N. G. Van

  - LECTURE NOTES IN COMPUTER SCIENCE - Year 2002

  Przedstawiona zostaje technika reprezentacji modeli języka w przetwarzaniu języka naturalnego wymagająca mało pamięci. Po krótkim omówieniu przyczyn poszukiwania oszczędnej reprezentacji takich modeli języka, pokazane jest, jak automaty skończone mogą być użyte w tym celu. Technika może być postrzegana jako zastosowanie i rozszerzenie doskonałej funkcji mieszającej z wykorzystaniem automatów skończonych. Pierwsze doświadczenia...

• Finite-state lexical tools

  Publication

  • J. Daciuk

  - Year 2004

  Artykuł przedstawia trzy pakiety oprogramowania zawierające narzędzia poziomu leksykalnego wykorzystujące automaty skończone: dwa zbiory samodzielnych programów i skryptów pomocniczych - jeden używający prostych automatów skończonych, drugi używający automatów Mealy`ego oraz bibliotekę funkcji. Wszystkie przedstawione pakiety posiadają podobne funkcje. Zamiast opisywać poszczególne pakiety, opis skupiony jest na dostarczanych przez...