An efficient incremental DFA minimization algorithm

Jan Daciuk; Bruce W. Watson

doi:10.1017/s1351324903003127

An efficient incremental DFA minimization algorithm

Abstract

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.

Citations

2 5

CrossRef
0

Web of Science
3 7

Scopus

Authors (2)

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

Cite as

Full text

full text is not available in portal

Keywords

Details

Category:: Articles
Type:: artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Published in:: Natural Language Engineering no. 9, edition 1, pages 49 - 64,
ISSN: 1351-3249
Language:: English
Publication year:: 2003
Bibliographic description:: Daciuk J., Watson B.: An efficient incremental DFA minimization algorithm// Natural Language Engineering. -Vol. 9., iss. 1 (2003), s.49-64
DOI:: Digital Object Identifier (open in new tab) 10.1017/s1351324903003127
Verified by:: Gdańsk University of Technology