ON THE EXPRESSIVE POWER OF SOME DYNAMIC LOGICS
Alexei P. Stolboushkin · Mathematics of the USSR-Sbornik · 1986
The relative expressive strength of dynamic logics of deterministic and nondeterministic programs is studied. It is known that the connectedness of a unoid is expressible in a dynamic logic of nondeterministic regular programs. Nonexpressibility of such connectedness in a dynamic logic of deterministic context-free programs is proved. The main result is a theorem on uniform periodicity of deterministic programs on a unoid projected into a Burnside group.This overlaps a known result to the effect that a dynamic logic of deterministic regular programs is less expressive than a dynamic logic of nondeterministic regular programs, and it shows that nondeterminism increases the expressive power of a dynamic logic even when a stack memory is used.Bibliography: 10 titles.