Affordable Access

Publisher Website

On static logics, dynamic logics, and complexity classes

Authors
Journal
Information and Control
0019-9958
Publisher
Elsevier
Publication Date
Volume
60
Identifiers
DOI: 10.1016/s0019-9958(84)80023-6
Disciplines
  • Logic
  • Mathematics

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.