×

The comparison of the expressive power of first-order dynamic logics. (English) Zbl 0536.03015

The paper presents basic results concerning the expressive power of dynamic logics. The main result is the proof that the deterministic regular logic is strictly weaker than regular logic. Some new open problems are stated.
Reviewer: J.Zlatuska

MSC:

03C07 Basic properties of first-order languages and structures
03B60 Other nonclassical logic
68Q65 Abstract data types; algebraic specification
68Q60 Specification and verification (program logics, model checking, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adian, S. I., The Burnside Problem and Identities in Groups (1979), Springer: Springer Berlin · Zbl 1343.20040
[2] Aho, A. V.; Ullman, J. D., The Theory of Parsing, Translation and Compiling, Vol 1: Parsing (1972), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0264.68032
[3] Belyaev, V. Ja.; Taitslin, M. A., On elementary properties of existentially-closed structures, Usp. Matem. Nauk, 34, 2, 39-94 (1979), (in Russian)
[4] Boyarskaya, Z. A.; Repin, N. N.; Taitslin, M. A., The deterministic dynamic logic is strictly weaker than the dynamic logic, (Mustafin, T. G., The problems of the Algebraic System Theory (1981), Karaganda University: Karaganda University Karaganda), 20-31, (in Russian)
[5] Erimbetov, M. M., On the expressive power of program logics, (Taitslin, M. A., Study on the Theoretical Programming (1981), Kazkh University: Kazkh University Alma-Ata), 49-68, (in Russian)
[6] Harel, D., First-order Dynamic Logic (1979), Springer: Springer Berlin · Zbl 0403.03024
[7] Harel, D., Logics of programs: Axiomatics and descriptive power, MIT/LCS/TM-200 (1978)
[8] Meyer, A. R.; Winklmann, K., On the expressive power of dynamic logic, MIT/LCS/TM-157 (1980)
[9] Shoenfield, J. R., Mathematical Logic (1967), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0155.01102
[10] Tiuryn, J., Review on ‘D. Harel, First-order dynamic logic’, J. Symbolic Logic, 47, 453-454 (1982)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.