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.
Authors
- dr hab. inż. Jan Daciuk link open in new tab ,
- Bruce W. Watson
Additional information
- DOI
- Digital Object Identifier link open in new tab 10.1017/s1351324903003127
- Category
- Publikacja w czasopiśmie
- Type
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Language
- angielski
- Publication year
- 2003
