О выразительной силе некоторых динамических логик

Изучается сравнительная выразительная сила динамических логик детерминированных и недетерминированных программ. Известно, что в динамической логике недетерминированных регулярных программ выразима связность уноида. В работе доказана невыразимость последней в динамической логике детерминированных контекстно-свободных программ. Основной является теорема о равномерной периодичности детерминированных программ на уноиде, строящемся в Бернсайдовой группе.
Это перекрывает известный результат о том, что динамическая логика детерминированных регулярных программ менее выразительна, чем динамическая логика недетерминированных регулярных программ, и показывает, что недетерминизм увеличивает выразительную мощь динамической логики даже при использовании магазинной памяти.
Библиография: 10 названий.