Многоаспектная минимизация недетерминированных конечных автоматов

недетерминированные конечные автоматы недетерминированные автоматы базисные автоматы конечные автоматы вершинная минимизация дуговая минимизация эквивалентные преобразования

Моделирование экономической деятельности малых предприятий, Переход металл-диэлектрик в периодической модели Андерсона-Хаббарда в случае 3-кратного вырождения, ...

Б. Ф. Мельников, А. А. Мельникова МНОГОАСПЕКТНАЯ МИНИМИЗАЦИЯ НЕДЕТЕРМИНИРОВАННЫХ КОНЕЧНЫХ АВТОМАТОВ (ЧАСТЬ I. <...> В первой части настоящей статьи рассматриваются некоторые вспомогательные алгоритмы, необходимые одновременно для двух проблем минимизации недетерминированных конечных автоматов – вершинной и дуговой. <...> Приводится несложный алгоритм минимизации детерминированных автоматов, с помощью которого производится одновременное построение функций разметки состояний. <...> Доказываются вспомогательные утверждения о входных языках состояний базисного автомата, необходимые для алгоритмов эквивалентного преобразования произвольных недетерминированных конечных автоматов. <...> Ключевые слова: недетерминированный конечный автомат, базисный автомат, алгоритмы эквивалентного преобразования, вершинная минимизация, дуговая минимизация. <...> Введение В первой части данной статьи рассматриваются вопросы, связанные с проблемой минимизации недетерминированных конечных автоматов, причем как по числу вершин, так и по числу дуг. <...> Приводятся вспомогательные утверждения и алгоритмы, нужные для решения этих задач, причем необходимые как для точного решения, так и для описания приближенных алгоритмов реального времени (anytime-алгоритмов). <...> ). В разделе 2 приводится несложный алгоритм минимизации детерминированных автоматов, с его помощью производится одновременное построение функций разметки состояний. <...> В разделе 3 доказываются вспомогательные утверждения о входных языках состояний базисного автомата, необходимые для алгоритмов эквивалентного преобразования произвольных недетерминированных конечных автоматов. <...> Поволжский регион наши приложения для разработки алгоритмов в [6, 7], где рассматривались anytime-алгоритмы (алгоритмы реального времени) для задачи дуговой минимизации. <...> В-третьих, мы иногда используем алгоритм добавления дуги; используя терминологию монографии [8], такое врйменное ухудшение возможного <...>

• Похожие документы из РУАЭСТ
• |
• Похожие документы из Руконт