Geodesic
On the expressive power of some dynamic logics
Sbornik. Mathematics, Tome 53 (1986) no. 2, pp. 411-419 
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/
@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},
     year = {1986},
     volume = {53},
     number = {2},
     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
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
%U http://geodesic.mathdoc.fr/item/SM_1986_53_2_a7/
%G en
%F SM_1986_53_2_a7

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.

[1] Harel D., First-order Dynamic Logic, Springer, Berlin, 1979 | MR | Zbl

[2] Meyer A. R., Winklmann K., “Expressing program looping in regular dynamic logic”, Theor. Comp. Sci., 18 (1982), 301–323 | DOI | MR

[3] Tiuryn J., “Review: D. Harel, “First-order dynamic logic””, J. Symb. Logic, 47 (1982), 453–454 | DOI

[4] Taitslin M. A., “Pyat voprosov o programmnykh logikakh”, Issledovaniya po teorii modelei, Izd-vo KazGU, Alma-Ata, 1982, 65–70

[5] Berman P., Halpern J. Y., Tiuryn J., “On the power of nondeterminism in Dynamic Logic”, Autom., Lamguages and Prog., Springer, Berlin, 1982, 48–60 | MR

[6] Adyan S. I., Problema Bernsaida i tozhdestva v gruppakh, Nauka, M., 1975 | MR | Zbl

[7] Urzyczyn P., Deterministic Context-Free Dynamic Logic is more expressive than Deterministic. Dynamic Logic of Regular Programms, FCT-83. Proceedings, Springer, Berlin, 1983 | MR

[8] Stolboushkin A. P., Taitslin M. A., “The comparison of the expressive power of firstorder dynamic logics”, Theor. Comp. Sci., 27 (1983) | DOI | MR | Zbl

[9] Stolbushkin A. P., Taitslin M. A., “Rol determinizma v logikakh programm”, III Konf. Primenenie metodov mat. logiki. Tez. dokl. (Tallin, IK AN ESSR), 158

[10] Taitslin M. A., “Ierarkhii programmnykh logik”, Sib. matem. zhurn., 24:3 (1983), 184–192 | MR