Управляющие системы и машины, №3, 2016, стаття 7
DOI: https://doi.org/10.15407/usim.2016.03.061
Чеботарев А. Н. О минимизации автоматов алгоритмом Хопкрофта. Управляющие системы и машины. 2016. № 3. C. 61-70.
УДК 519.713
А.М. Чеботарев, д.т.н., Інститут кібернетики імені В.М. Глушкова НАН України, просп. Глушкова, 40, Київ, 03187, Україна
Про мінімізацію автоматів алгоритмом Хопкрофта
Розглянуто алгоритм Хопкрофта для мінімізації детермінованих всюди визначених скінченних автоматів. Дано зрозуміле до
ведення коректності алгоритму та оцінки часової складності. Доведення базується на запропонованому понятті дерева розще
плень і методі розповсюдження «закритих» вузлів у цьому дереві.
Завантажити повний текст PDF (російською).
Ключові слова: алгоритм Хопкрофта, мінімізація автомата, розбиття, конгруенція, часова складність, дерево розщеплень.
Надійшла 11.03.2016
