Deterministic propositional dynamic logic: finite models, complexity, and completeness
Standard modal operators \( \langle \rangle \) may be thought of as standing for fixed accessibility relations \( R \). Thus \(\langle \rangle_{p} \| \) is the proposition (set of possible worlds) \( R^{\prime \prime}|p| \), where \( |p| \) is the proposition expressed by \( p \). Dynamic logic is a generalization of modal logic with explicit free variables ranging over accessibility relations, or programs. Thus \(|\langle a\rangle_{p} | \) is the proposition (set of possible states) \(|a|{\prime \prime}|p| \), where \( |a| \) is the program designated by a. Certain operations on relations (programs) are also assumed. Deterministic propositional dynamic logic (DPDI), as the authors call it, incorporates the further assumption that every atomic program is a function. A construction of finite models for arbitrary satisfiable DPDL sentences is given, yielding a decision procedure that runs in deterministic time \( 2^{c n} \). The decision procedure is streamlined by the use of partial models. DPDI is axiomatized by adding \( \langle\mathbf{A}\rangle \mathbf{p} \rightarrow[\mathbf{A}] \mathbf{p} \) for atomic A to K. Segerberg's axioms for PDI ( [] being the dual of \(\langle\rangle\)). The authors prove that this axiomatization is semantically complete.
- Automata-theoretic techniques for modal logics of programs
- Satisfiability in many-valued sentential logic is NP-complete
- A modal perspective on the computational complexity of attribute value grammar
- The price of universality
- Propositional dynamic logic with quantification over regular computation sequences
- Program schemata technique for propositional program logics: a 30-year history
- Decision procedures and expressiveness in the temporal logic of branching time
- Mechanizing common knowledge logic using COQ
- Modal restriction semigroups: towards an algebra of functions.
- Modal logics for reasoning about infinite unions and intersections of binary relations
- Separation logics and modalities: a survey
- A propositional dense time logic
- Dynamic logic as a uniform framework for theorem proving in intensional logic
- Interpolation for converse PDL
- A complete propositional dynamic logic for regular expressions with lookahead
- The propositional dynamic logic of deterministic, well-structured programs
- An essay in combinatory dynamic logic
- Determinism and looping in combinatory PDL
This page was built for publication: Deterministic propositional dynamic logic: finite models, complexity, and completeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1839245)