Разработка метода, нацеленного на распознавание эквивалентности детерминированных многоленточных автоматов путем эквивалентных преобразований их структуры. Описание циклов, полученных трансформацией автомата. Применимость трансформационного метода.
Автореферат диссертации на соискание ученой степени доктора физико-математических наук специальность 01.01.09 дискретная математика и математическая кибернетика Работа выполнена в Белгородском государственном университете на факультете компьютерных наук и телекоммуникаций Официальные оппоненты: член-корреспондент НАНУ, доктор физико-математических наук, профессор Летичевский Александр Адольфович доктор физико-математических наук, профессор Сапоженко Александр Антонович доктор физико-математических наук, профессор Ломазова Ирина АлександровнаПолнота системы трактуется как существование алгоритма, который для любой пары эквивалентных автоматов из данного множества строит конечную цепочку преобразований, принадлежащих этой системе и переводящих один автомат, принадлежащий паре, в другой принадлежащий ей автомат. Он основан на необходимом признаке d: если два автомата эквивалентны, то существует соответствие между циклами одного и другого автомата, при котором описания соответствующих друг другу циклов являются кратными некоторому общему для них шаблону; кроме того, выходы к соответствующим друг другу циклам не противоречат отношению эквивалентности автоматов. В случае, когда проверка признака d закончилась успешно, во втором автомате уже имеются образы описаний всех циклов первого автомата, поэтому и достаточна работа со вторым автоматом. Для автоматов с непересекающимися циклами, принадлежащих множеству Mn,m, n, m ? 2, получен следующий результат: для двух произвольных автоматов, поступивших на вход метода, дана оценка глубины выполняемого методом процесса развертки, достаточной, чтобы установить либо их неэквивалентность путем нарушения признака d, либо выполнимость условия a, гарантирующего их эквивалентность (теорема 3.4). Решение проблемы минимизации в M осуществлено следующим образом: построена система T э. п. автоматов, полная в M (теорема 4.1), при этом доказательство полноты проведено традиционным образом: трансформацией средствами системы каждого автомата из M в канонический; таким образом, построен алгоритм, разрешающий эквивалентность в M (утверждение 4.
Вы можете ЗАГРУЗИТЬ и ПОВЫСИТЬ уникальность своей работы
