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.
Autorzy
- dr hab. inż. Jan Daciuk link otwiera się w nowej karcie ,
- Bruce W. Watson
Informacje dodatkowe
- DOI
- Cyfrowy identyfikator dokumentu elektronicznego link otwiera się w nowej karcie 10.1017/s1351324903003127
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Język
- angielski
- Rok wydania
- 2003
Źródło danych: MOSTWiedzy.pl - publikacja "An efficient incremental DFA minimization algorithm" link otwiera się w nowej karcie
