Decision complexity of variants of propositional dynamic logic
Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45) Other nonclassical logic (03B60) Complexity of computation (including implicit computational complexity) (03D15) General topics in the theory of software (68N01) Abstract data types; algebraic specification (68Q65)
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.]
- The propositional dynamic logic of deterministic, well-structured programs
- Propositional dynamic logic of nonregular programs
- Complexity optimal decision procedure for a propositional dynamic logic with parallel composition
- Propositional dynamic logic with recursive programs
- Complexity and expressivity of propositional dynamic logics with finitely many variables
- Dynamic process logic
- On the computational complexity of satisfiability in propositional logics of programs
- \(\Pi_ 1^ 1\)-universality of some propositional logics of concurrent programs
- Deterministic propositional dynamic logic: finite models, complexity, and completeness
- Program schemata technique for propositional program logics: a 30-year history
- Loop-type sequent calculi for temporal logic
- Complexity optimal decision procedure for a propositional dynamic logic with parallel composition
- Decidability and expressivity of Ockhamist propositional dynamic logics
- Proving the decidability of the \(\mathrm{PDL}\times\mathrm{PDL}\) product logic
- scientific article; zbMATH DE number 3880104 (Why is no real title available?)
- A Reduction from DLP to PDL
- scientific article; zbMATH DE number 5599076 (Why is no real title available?)
- scientific article; zbMATH DE number 3983144 (Why is no real title available?)
- A derivation-loop method for temporal logic
- More efficient proof-search for sequents of temporal logic
- Complexity and expressivity of propositional dynamic logics with finitely many variables
- Wreath products of distributive forest algebras
- Dynamic logic of propositional assignments: a well-behaved variant of PDL
- Computer Science Logic
- A lower complexity bound for propositional dynamic logic with intersection
- 2-Exp Time lower bounds for propositional dynamic logics with intersection
- The propositional dynamic logic of deterministic, well-structured programs
- Decidability of finite probabilistic propositional dynamic logics
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)