Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

180 А. Розенберг
(б) R(/z) замкнут относительно объединения и пересечения с регулярными множествами;
(в) R(/z) замкнут относительно умножения справа на регулярное множество;
(г) R(n) замкнут относительно отображения, обратного к осуществляемому на ОПМ;
(д) R(n) замкнут относительно минимизации.
Замечание. R(l) не замкнут ни относительно объединения и пересечения, ни относительно отображения, обратного к осуществляемому на ПРВ.
Более подробное изучение R(/z) является предметом дальнейших исследований.
4. СВОЙСТВА НЕЗАМКНУТОСТИ
Приведем примеры некоторых операций, не сохраняющих определимость в реальное время.
4.1. Сцепление. Доказывается незамкнутость R относительно сцепления даже с регулярными множествами. Доказательство опирается на ряд определений и лемм.
Определение 5. Пусть А — множество слов. Бинарное отношение ?/t(mod Л) для слов х и у определяется следующим образом: xEky(modA), если для всех слов г длины, не превышающей k, слово xz принадлежит А тогда и только тогда, когда слово yz принадлежит А.
Очевидно, ?fe(modA) является отношением эквивалентности.
Лемма 1 (Хартманис и Стирнз [5]). Если Т есть п-МРВ с d состояниями и w рабочими символами (включая /), то число классов эквивалентности l) no ?/j(mod А (Т)) не может превосходить d-w(2h+])n.
Ограничимся рассмотрением того случая, когда алфавит 2 имеет по меньшей мере две буквы. Можно предположить, что (О, 1} <= S.
Определим язык2)
Лемма 2. Язык Р определим в реальное время.
В самом деле Р определим в реальное время PDS-автоматом (Гинзбург и Грейбах [2]).
Наша цель показать, что 2*Р не определим в реальное время. Мы выполним это, исследуя скорость роста индекса отношения Eft(modS*P).
) Называемое индексом отношения. — Прим. ред. ) t'r — инверсия (обращение) слова t. — Прим ред.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 181 182 183 184 185 186 187 188 189 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика