УСиМ: Управляющие системы и машины : междунар. науч. журн. - 2016. - N 3. - С. 61-70. - Библиогр. в конце ст. - ISSN 0130-5395.
(Шифр в БД У481695/2016/3)

Ключові слова: алгоритм хопкрофта -- алгоритм хопкрофта -- минимизация автомата -- мінімізація автомата -- разбиение -- розбиття -- конгруэнция -- конгруенція -- временная сложность -- часова складність -- дерево расщеплений -- дерево розщеплень --
Анотація:
Рассмотрен алгоритм Хопрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения "закрытых" вершин в этом дереве.
Розглянуто алгоритм Хопрофта для мінімізації детермінованих всюди визначених скінчених автоматів. Дано зрозуміле доведення коректності алгоритму і оцінки часової складності. Доказ засноване на запропонованому понятті дерева розщеплення і методі розпосюдження "закритих" вузлів в цьому дереві.