EN|RU

Том 19, номер 2, 2012 г., Стр. 3-18

УДК 510.53
Вялый М. Н., Рубцов А. А. 
Алгоритмическая разрешимость задач о поведении автоматов на сверхсловах

Аннотация:
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая — при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача регулярной реализуемости (проверки выполнимости некоторого регулярного свойства на заданном множестве слов) алгоритмически эквивалентна некоторой задаче о достижении автоматом принимающего состояния при чтении сверхслова.
Библиогр. 11.

Ключевые слова: сверхслово, регулярный язык, алгоритмическая разрешимость, монадическая теория.

Вялый Михаил Николаевич 1
Рубцов Александр Александрович 2

1. Вычислительный центр РАН,
ул. Вавилова, 40, 119333 Москва, Россия
2. Московский физико-технический институт,
Институтский пер., 9, 141700 Долгопрудный, Россия
е-mail: vyalyi@gmail.com, rubtsov99@gmail.com

Статья поступила 6 июня 2011 г.
Исправленный вариант — 9 сентября 2011 г.

 © Институт математики им. С. Л. Соболева, 2015