The comparison of the expressive power of first-order dynamic logics

AbstractThis paper gives an account of results which answer some questions from Harel (1978, 1979), Meyer and Winklmann (1980) and Tiuryn (1982). In particular it is shown that the deterministic regular logic is strictly weaker than the regular logic, the context-free logic strictly weaker than the finitely generated recursive logic, the recursive logic strictly weaker than the weak ω-order logic, and the recursive logic strictly stronger than the finitely generated recursive logic. Some well-known and new open problems are stated