zbMATH — the first resource for mathematics

On static logics, dynamic logics, and complexity classes. (English) Zbl 0589.68030
Summary: Several versions of quantified dynamic logic are shown to be equivalent in expressive power to ”static” extensions of classical logics. Consequently, by recent results of various researchers, many connections between dynamic logics and complexity classes are obtained. Among other things, a sequence of dynamic logics of increasing expressive power, which correspond, over appropriate finite structures, to LOGSPACE, PTIME, and PSPACE, as well as to the sets definable in the logarithmic-space, polynomial-time, and arithmetical hierarchies is exhibited.

68Q65 Abstract data types; algebraic specification
68Q25 Analysis of algorithms and problem complexity
03D15 Complexity of computation (including implicit computational complexity)
03B45 Modal logic (including the logic of norms)
03B10 Classical first-order logic
Full Text: DOI