On static logics, dynamic logics, and complexity classes

DOI10.1016/S0019-9958(84)80023-6zbMath0589.68030MaRDI QIDQ3718149

David Harel, David Peleg

Publication date: 1984

Published in: Information and Control (Search for Journal in Brave)

zbMATH Keywords

expressive powerPSPACEPTIMELOGSPACEquantified dynamic logic

Mathematics Subject Classification ID

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

Related Items

Complexity of proving program correctness, Program Schemes with Deep Pushdown Storage, Expressing program looping in regular dynamic logic, Query languages for hierarchic databases, Unnamed Item, On strictly arithmetical completeness in logics of programs, Propositional dynamic logic of regular programs, On the power of built-in relations in certain classes of program schemes, On the power of deep pushdown stacks, Program schemes, arrays, Lindström quantifiers and zero-one laws, Context-sensitive transitive closure operators, Logical and schematic characterization of complexity classes