Propositional Dynamic Logic with Program Quantifiers | Zendy

Daniël Leivant | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Propositional Dynamic Logic with Program Quantifiers

Author(s) -

Daniël Leivant

Publication year - 2008

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2008.10.014

Subject(s) - propositional variable , zeroth order logic , dynamic logic (digital electronics) , propositional calculus , expressive power , computer science , extension (predicate logic) , autoepistemic logic , mathematics , context (archaeology) , hierarchy , intermediate logic , calculus (dental) , theoretical computer science , discrete mathematics , algorithm , programming language , multimodal logic , description logic , medicine , paleontology , physics , dentistry , transistor , voltage , quantum mechanics , economics , market economy , biology

We consider an extension QPDL of Segerberg-Pratt's Propositional Dynamic Logic PDL, with program quantification, and study its expressive power and complexity. A mild form of program quantification is obtained in the calculus μPDL, extending PDL with recursive procedures (i.e. context free programs), which is known to be Π11-complete. The unrestricted program quantification we consider leads to complexity equivalent to that of second-order logic (and second-order arithmetic), i.e. outside the analytical hierarchy. However, the deterministic variant of QPDL has complexity Π11

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research