Decision complexity of variants of propositional dynamic logic

From MaRDI portal





Deterministic propositional dynamic logic (DPDL) is a variant of propositional dynamic logic (PDL) in which any elementary program is interpreted as a partial function. This paper, by elaborating the methods of Fischer/Ladner and Pratt, shows that the satisfiability problem of DPDL can be decided in deterministic exponential time and that there is a constant \(c\) such that the satisfiability problem for DPDL cannot be decided in deterministic time \(c^{n/\log n}\). The paper shows also that another variant of PDL with the shuffle operator and its closure is not axiomatizable. [For the entire collection see Zbl 0435.00014.]




Cited in
(23)








This page was built for publication: Decision complexity of variants of propositional dynamic logic

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