Место издания:Изд-во механико-математического факультета МГУ
Первая страница:272
Последняя страница:275
Аннотация:Конечный автомат-преобразователь (трансдьюсер) является, вероятно, самым простым расширением широко известной модели вычислений автоматов Мили, при котором происходит существенное возрастание вычислительных возможностей модели. Оказалось, что трансдьюсеры удобно использовать в качестве моделей трансляторов в области математической лингвистики, а также в качестве моделей реагирующих вычислительных систем (драйверов, контроллеров, коммутаторов). Однако было обнаружено, что некоторые задачи анализа поведения трансдьюсеров алгоритмически неразрешимы. Неразрешимой является проблема эквивалентности для автоматов-преобразователей, и неразрешимость сохраняется даже в том случае, когда входной алфавит автомата состоит из одной буквы. В стремлении уточнить, какие особенности управляющей структуры и вычислений автоматов неизбежно сопутствуют алгоритмической трудности анализа поведения трансдьюсеров были предприняты исследования по выделению как можно более обширных классов автоматов-преобразователей с разрешимой проблемой эквивалентности. Вначале было показано, что проблема эквивалентности эффективно разрешима для детерминированных трансдьюсеров, а затем было установлено, что проблема эквивалентности остается разрешимой также и для некоторых классов недетерминированных трансдьюсеров, в которых неоднозначность преобразования входных слов в выходные ограничена по мощности множеств выходных слов, которые порождаются автоматом при вычислениях над заданным входным словом, или по разнообразию длин выходных слов. Возникло предположение о том, что при нарушении этих ограничений разрешимость проблемы эквивалентности трансдьюсеров уже не удастся сохранить.
В данной статье мы продолжаем поиск и исследование новых классов недетерминированных автоматов-преобразователей с разрешимой проблемой эквивалентности. Цель исследования - провести как можно более точную и подробную демаркацию границы между разрешимыми и неразрешимыми случаями проблемы эквивалентности для рассматриваемой модели вычислений. Мы рассматриваем один класс недетерминированных автоматов, работающих над выходным алфавитом из одной буквы. Характерная особенность рассматриваемых автоматов-преобразователей состоит в том, что для каждого состояния автомата и любой буквы входного алфавита новое состояние, в которое может осуществиться переход, определяется однозначно, но выходные слова на этих переходах могут быть разными. Таким образом, для каждого входного слова разнообразие выходных слов, порождаемых автоматом, может варьироваться сколь угодно широко, как по мощности, так и по длине слов. Нам удалось показать, что проблема эквивалентности в указанном классе автоматов-преобразователей разрешима.