Regular dynamic logic is not interpretable in deterministic context-free dynamic logic

In (A. P. Stolboushkin and M.A. Taitslin, Inform. Contr. 57 (1983), 48–55) Taitslin introduced a structure G(A) in which every deterministic regular program is uniformly periodic. In the present paper it is proved that every deterministic context-free program is also uniformly periodic in the same structure. Hence, in the theory of G(A) each formula of deterministic dynamic logic of context-free programs is equivalent to a first-order formula. However, for regular dynamic logic this statement is false. We then show that regular dynamic logic is not interpretable in deterministic context-free dynamic logic. Thus, deterministic context-free dynamic logic is strictly weaker than context-free dynamic logic. The proof holds in the presence of first-order tests (and even “rich” tests) as well as quantifier-free tests