Том 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 г.
Литература
[1] Вялый М. Н. О моделях недетерминизма для двусторонних автоматов // Тр. VIII междунар. конф. «Дискретные модели в теории управляющих систем». — М.: МаксПресс, 2009. — С. 54–60.
[2] Вялый М. Н., Тарасов С. П. Орбиты линейных отображений и свойства регулярных языков // Дискрeт. анализ и исслед. операций. — 2010. — Т. 17, № 6. — С. 20–49.
[3] Мучник Ан. А., Притыкин Ю. Л., Семенов А. Л. Последовательности, близкие к периодическим // Успехи мат. наук. — 2009. — Т. 64, вып. 5. — С. 21–96.
[4] Семенов А. Л. Логические теории одноместных функций на натуральном ряде // Изв. АН СССР. Сер. мат. — 1983. — Т. 47, вып. 3. — С. 623–658.
[5] Bailey D. H., Crandall R. E. On the random character of fundamental constant expansions // Exp. Math. — 2001. — Vol. 10, N 2. — P. 175–190.
[6] Bárány V. A hierarchy of automatic $\omega$-words having a decidable MSO theory // Theor. Inform. Appl. — 2008. — Vol. 42. — P. 417–450.
[7] Büchi J. R. On a decision method in restricted second-order arithmetic // Proc. Int. Congress Logic, Methodology, and Philosophy of Science. — Palo Alto: Stanford Univ. Press, 1962. — P. 1–11.
[8] Carton O., ThomasW. The monadic theory of morphic infinite words and generalizations // Inf. Comput. — 2002. — Vol. 176, N 1. — P. 51–65.
[9] McNaughton R. Testing and generating infinite sequences by a finite automaton // Inf. Control. — 1966. — Vol. 9. — P. 521–530.
[10] Roggenbach M. Determinization of Büchi-automata // Automata, logics, and infinite games. — New York; Heidelberg; Berlin: Springer-Verl., 2002. — P. 43–60 (Lect. Notes Comput. Sci.; Vol. 2500).
[11] Vyalyi M. N. On models of a nondeterministic computation // Proc. CSR 2009. — New York; Heidelberg; Berlin: Springer-Verl., 2009. — P. 334–345 (Lect. Notes Comput. Sci.; Vol. 5675).
