|
Эта публикация цитируется в 1 научной статье (всего в 1 статье)
О выразительной силе некоторых динамических логик
А. П. Столбоушкин
Аннотация:
Изучается сравнительная выразительная сила динамических логик детерминированных и недетерминированных программ. Известно, что в динамической логике недетерминированных регулярных программ выразима связность уноида. В работе доказана невыразимость последней в динамической логике детерминированных контекстно-свободных программ. Основной является теорема о равномерной периодичности детерминированных программ на уноиде, строящемся в Бернсайдовой группе.
Это перекрывает известный результат о том, что динамическая логика детерминированных регулярных программ менее выразительна, чем динамическая логика недетерминированных регулярных программ, и показывает, что недетерминизм увеличивает выразительную мощь динамической логики даже при использовании магазинной памяти.
Библиография: 10 названий.
Поступила в редакцию: 11.01.1983 и 25.01.1984
Образец цитирования:
А. П. Столбоушкин, “О выразительной силе некоторых динамических логик”, Матем. сб., 125(167):3(11) (1984), 410–419; A. P. Stolboushkin, “On the expressive power of some dynamic logics”, Math. USSR-Sb., 53:2 (1986), 411–419
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/sm2092 https://www.mathnet.ru/rus/sm/v167/i3/p410
|
Статистика просмотров: |
Страница аннотации: | 315 | PDF русской версии: | 86 | PDF английской версии: | 3 | Список литературы: | 35 |
|