On static logics, dynamic logics, and complexity classes

DOI10.1016/S0019-9958(84)80023-6MaRDI QIDQ3718149zbMATH OpenFDO

Authors David Harel, David Peleg

Publication date 1984

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

Full work available at URL https://doi.org/10.1016/S0019-9958(84)80023-6

zbMATH Keywords

expressive powerLOGSPACEPSPACEPTIMEquantified dynamic logic

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4179344
• The comparison of the expressive power of first-order dynamic logics
• ON THE EXPRESSIVE POWER OF SOME DYNAMIC LOGICS
• scientific article; zbMATH DE number 4112562
• Propositional dynamic logic with program quantifiers

Cited in

(15)

• On the power of deep pushdown stacks
• A simple dynamic logic
• Expressing program looping in regular dynamic logic
• Query languages for hierarchic databases
• Propositional dynamic logic of regular programs
• On the power of built-in relations in certain classes of program schemes
• Context-sensitive transitive closure operators
• Logical and schematic characterization of complexity classes
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• On strictly arithmetical completeness in logics of programs
• scientific article; zbMATH DE number 4179344 (Why is no real title available?)
• Program Schemes with Deep Pushdown Storage
• ON THE EXPRESSIVE POWER OF SOME DYNAMIC LOGICS
• Expressivity within second-order transitive-closure logic
• Complexity of proving program correctness

This page was built for publication: On static logics, dynamic logics, and complexity classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3718149)