An efficient incremental DFA minimization algorithm - Publikacja - MOST Wiedzy

Wyszukiwarka

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

  • 0

    CrossRef

  • 0

    Web of Science

  • 0

    Scopus

Pełna treść

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

wyświetlono 15 razy

Publikacje, które mogą cię zainteresować

Meta Tagi