An efficient incremental DFA minimization algorithm

Jan Daciuk; Bruce W. Watson

doi:10.1017/s1351324903003127

An efficient incremental DFA minimization algorithm

Abstrakt

W tym artykule przedstawiamy nowy algorytm minimalizacji deterministycznego automatu skończonego. Algorytm jest przyrostowy - może być zatrzymany w dowolnym momencie, dając częściowo zminimalizowany automat. Wszystkie inne (znane) algorytmy minimalizacji dają wyniki pośrednie nieprzydatne dla częściowej minimalizacji. Ponieważ pierwszy algorytm jest łatwo zrozumiały ale mało wydajny, rozważamy trzy praktyczne, znaczące usprawnienia. Pierwsze dwa nie wpływają na asymptotyczny czas wykonania w najgorszym przypadku, chociaż sprawują się dobrze na dużej klasie automatów. Trzecie usprawnienie przynosi algorytm o kwadratowej złożoności obliczeniowej, który jest konkurencyjny w stosunku do wcześniejszych algorytmów.

Cytowania

2 5

CrossRef
0

Web of Science
3 7

Scopus

Autorzy (2)

Jan Daciuk dr hab. inż.
Bruce W. Watson

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Kategoria:: Publikacja w czasopiśmie
Typ:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Opublikowano w:: Natural Language Engineering nr 9, wydanie 1, strony 49 - 64,
ISSN: 1351-3249
Język:: angielski
Rok wydania:: 2003
Opis bibliograficzny:: Daciuk J., Watson B.: An efficient incremental DFA minimization algorithm// Natural Language Engineering. -Vol. 9., iss. 1 (2003), s.49-64
DOI:: Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1017/s1351324903003127
Weryfikacja:: Politechnika Gdańska