Geodesic
On the expressive power of some dynamic logics
Sbornik. Mathematics, Tome 53 (1986) no. 2, pp. 411-419

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{SM_1986_53_2_a7,
     author = {A. P. Stolboushkin},
     title = {On the expressive power of some dynamic logics},
     journal = {Sbornik. Mathematics},
     pages = {411--419},
     publisher = {mathdoc},
     volume = {53},
     number = {2},
     year = {1986},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_1986_53_2_a7/}
}
TY  - JOUR
AU  - A. P. Stolboushkin
TI  - On the expressive power of some dynamic logics
JO  - Sbornik. Mathematics
PY  - 1986
SP  - 411
EP  - 419
VL  - 53
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SM_1986_53_2_a7/
LA  - en
ID  - SM_1986_53_2_a7
ER  - 
%0 Journal Article
%A A. P. Stolboushkin
%T On the expressive power of some dynamic logics
%J Sbornik. Mathematics
%D 1986
%P 411-419
%V 53
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SM_1986_53_2_a7/
%G en
%F SM_1986_53_2_a7
A. P. Stolboushkin. On the expressive power of some dynamic logics. Sbornik. Mathematics, Tome 53 (1986) no. 2, pp. 411-419. http://geodesic.mathdoc.fr/item/SM_1986_53_2_a7/