Geodesic
On dynamic theories of free algebras
Sbornik. Mathematics, Tome 66 (1990) no. 2, pp. 313-327 
I. Kh. Musikaev; M. A. Taitslin. On dynamic theories of free algebras. Sbornik. Mathematics, Tome 66 (1990) no. 2, pp. 313-327. http://geodesic.mathdoc.fr/item/SM_1990_66_2_a0/
@article{SM_1990_66_2_a0,
     author = {I. Kh. Musikaev and M. A. Taitslin},
     title = {On dynamic theories of free algebras},
     journal = {Sbornik. Mathematics},
     pages = {313--327},
     year = {1990},
     volume = {66},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_1990_66_2_a0/}
}
TY  - JOUR
AU  - I. Kh. Musikaev
AU  - M. A. Taitslin
TI  - On dynamic theories of free algebras
JO  - Sbornik. Mathematics
PY  - 1990
SP  - 313
EP  - 327
VL  - 66
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SM_1990_66_2_a0/
LA  - en
ID  - SM_1990_66_2_a0
ER  - 
%0 Journal Article
%A I. Kh. Musikaev
%A M. A. Taitslin
%T On dynamic theories of free algebras
%J Sbornik. Mathematics
%D 1990
%P 313-327
%V 66
%N 2
%U http://geodesic.mathdoc.fr/item/SM_1990_66_2_a0/
%G en
%F SM_1990_66_2_a0

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

A certain canonical form is introduced for formulas of the logic $L_{\infty\omega}(n)$, and it is proved that every formula of this logic is equivalent on free algebras to some canonical formula. This permits one to establish that no finite number of programs is sufficient to express all inquiries expressible in dynamic logic and involving the free algebra under consideration. Also obtained, as a corollary, are results to the effect that an infinite memory increases the expressive possibilities of dynamic logic. Bibliography: 7 titles.

[1] Maltsev A. I., “Ob elementarnykh teoriyakh lokalno-svobodnykh universalnykh algebr”, DAN SSSR, 138:5 (1961), 1009–1012 | Zbl

[2] Stolboushkin A. P., Taitslin M. A., “Dinamicheskie logiki”, Kibernetika i vychislitelnaya tekhnika, Vyp. 2, Nauka, M., 1986, 180–230 | MR

[3] Erimbetov M. M., “O vyrazitelnoi sile programmnykh logik”, Issledovaniya po teoreticheskomu programmirovaniyu, Izd-vo Kaz. un-ta, Alma-Ata, 1981, 49–68 | MR

[4] Berman P., Halpern J. Y., Tiuryn J., “On the Power of Nondeterminism in Dynamic Logic”, Automata, Languages and Programming, Springer, Berlin, 1982, 48–60 | MR

[5] Tiuryn J., “Implicit definability of finite binary trees by sets of equations”, Logic and Machines: Decision Problems and Complexity, Springer-Verlag, Berlin, 1984, 320–332 | MR

[6] Tiuryn J., “Umbounded Program Memory Adds to the Expressive Power of First-Order Programming Logic”, Information and Control, 60, no. 1–3, 1984, 12–35 | MR | Zbl

[7] Harel D., First-order dynamic logic, Springer-Verlag, Berlin, 1979 | MR | Zbl