О минимизации автоматов алгоритмом Хопкрофта

О минимизации автоматов алгоритмом Хопкрофта

Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в эт...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2016
Автор: Чеботарев, А.Н.
Формат: Стаття
Мова:Russian
Опубліковано: Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2016
Назва видання:Управляющие системы и машины
Теми:
Программная инженерия и программные средства
Онлайн доступ:http://dspace.nbuv.gov.ua/handle/123456789/113327
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id irk-123456789-113327
record_format dspace
spelling irk-123456789-1133272017-02-07T03:02:37Z О минимизации автоматов алгоритмом Хопкрофта Чеботарев, А.Н. Программная инженерия и программные средства Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве. Розглянуто алгоритм Хопкрофта для мінімізації детермінованих всюди визначених скінченних автоматів. Дано зрозуміле до ведення коректності алгоритму та оцінки часової складності. Доведення базується на запропонованому понятті дерева розщеплень і методі розповсюдження «закритих» вузлів у цьому дереві. The algorithm for minimizing deterministic complete finite state automata proposed by J. Hopcroft is considered. Although the existence of this algorithm is widely known, its theoretical justification is not that obvious. The aim of this study is to give a clear and understandable presentation of the algorithm focusing on the firm theoretical basis, rigorous correctness proof and time complexity analysis. The algorithm is based on the partition notion of the automaton states which defines the equivalence relation. It constructs a sequence of such partitions by a stepwise refinement of some initial partition. The last partition in this sequence corresponds to the maximal congruence on the automaton’s states, i.e., the equivalence stable with respect to the transition function of the automaton. To prove correctness of the algorithm it is necessary to show that the final constructed partition is a congruence, and that this congruence is maximal. In the first part of this proof, the introduced notion of binary splitting tree is used whose nodes are classes of the partitions constructing by the algorithm and a technique for extending the so called “closed” nodes of this tree. The second part is based on the proposition concerning the order on partitions. It is proved that every partition in the sequence generated by the algorithm is greater than or equal to the partition corresponding to the maximal congruence. It is show that Hopcroft’s algorithm can be implemented to worst-case time complexity O (kn log n) for an automaton with n states over a k-letter alphabet. This statement relies on the fact that the total number of actions refining the partitions over all steps of algorithm execution is of the order of O(kn log n). The data structures which allow obtaining this time complexity is presented. The last section describes the algorithm features for minimizing Moore and Mealy automata. 2016 Article О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос. 0130-5395 http://dspace.nbuv.gov.ua/handle/123456789/113327 519.713 ru Управляющие системы и машины Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
topic Программная инженерия и программные средства
Программная инженерия и программные средства
spellingShingle Программная инженерия и программные средства
Программная инженерия и программные средства
Чеботарев, А.Н.
О минимизации автоматов алгоритмом Хопкрофта
Управляющие системы и машины
description Рассмотрен алгоритм Хопкрофта для минимизации детерминированных вполне определенных конечных автоматов. Даны понятные доказательства корректности алгоритма и оценки временной сложности. Доказательство основано на предложенном понятии дерева расщеплений и методе распространения «закрытых» вершин в этом дереве.
format Article
author Чеботарев, А.Н.
author_facet Чеботарев, А.Н.
author_sort Чеботарев, А.Н.
title О минимизации автоматов алгоритмом Хопкрофта
title_short О минимизации автоматов алгоритмом Хопкрофта
title_full О минимизации автоматов алгоритмом Хопкрофта
title_fullStr О минимизации автоматов алгоритмом Хопкрофта
title_full_unstemmed О минимизации автоматов алгоритмом Хопкрофта
title_sort о минимизации автоматов алгоритмом хопкрофта
publisher Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
publishDate 2016
topic_facet Программная инженерия и программные средства
url http://dspace.nbuv.gov.ua/handle/123456789/113327
citation_txt О минимизации автоматов алгоритмом Хопкрофта / А.Н. Чеботарев // Управляющие системы и машины. — 2016. — № 3. — С. 61-70. — Бібліогр.: 8 назв. — рос.
series Управляющие системы и машины
work_keys_str_mv AT čebotarevan ominimizaciiavtomatovalgoritmomhopkrofta
first_indexed 2024-03-30T09:26:38Z
last_indexed 2024-03-30T09:26:38Z
_version_ 1796149978959183872

Схожі ресурси