|
Дискретный анализ и исследование операций, 2012, том 19, выпуск 2, страницы 3–18
(Mi da679)
|
|
|
|
Эта публикация цитируется в 2 научных статьях (всего в 2 статьях)
Алгоритмическая разрешимость задач о поведении автоматов на сверхсловах
М. Н. Вялыйa, А. А. Рубцовb a Вычислительный центр РАН, Москва, Россия
b Московский физико-технический институт, Долгопрудный, Россия
Аннотация:
Работа посвящена двум алгоритмическим задачам, связанным с анализом поведения конечного автомата при чтении сверхслова (бесконечной последовательности): достигает ли автомат принимающего состояния и достигает ли он принимающего состояния бесконечно часто. Первая задача возникает при анализе моделей обобщённого недетерминизма, а вторая – при анализе разрешимости монадических теорий второго порядка. Получены новые условия разрешимости для этих задач. Доказано, что всякая задача регулярной реализуемости (проверки выполнимости некоторого регулярного свойства на заданном множестве слов) алгоритмически эквивалентна некоторой задаче о достижении автоматом принимающего состояния при чтении сверхслова. Библиогр. 11.
Ключевые слова:
сверхслово, регулярный язык, алгоритмическая разрешимость, монадическая теория.
Статья поступила: 06.06.2011 Переработанный вариант: 09.09.2011
Образец цитирования:
М. Н. Вялый, А. А. Рубцов, “Алгоритмическая разрешимость задач о поведении автоматов на сверхсловах”, Дискретн. анализ и исслед. опер., 19:2 (2012), 3–18
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/da679 https://www.mathnet.ru/rus/da/v19/i2/p3
|
Статистика просмотров: |
Страница аннотации: | 537 | PDF полного текста: | 164 | Список литературы: | 48 | Первая страница: | 19 |
|