Deterministic Context-Free Dynamic Logic Is More Expressive than Deterministic Dynamic Logic of Regular Programs¹

Article type: Research Article

Authors: Urzyczyn, Pawel

Affiliations: Institute of Mathematics, University of Warsaw, 00-901 Warszawa, PKiN, Poland

Note: [1] An extended version of the paper [1], presented at the conference “Foundations of Computation Theory”, Borgholm, Sweden, 1983.

Abstract: We show an example of an algebra T∙, such that every flow-chart program is equivalent in T∙ to a loop-free approximation of itself, while a program augmented by one binary push-down store is not equivalent in T∙ to any loop-free program. From this we deduce that the Deterministic Dynamic Logic of regular programs is strictly weaker than the Deterministic Context-Free Dynamic Logic.

DOI: 10.3233/FI-1987-10203

Journal: Fundamenta Informaticae, vol. 10, no. 2, pp. 123-141, 1987