Deterministic propositional dynamic logic: finite models, complexity, and completeness

From MaRDI portal





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.











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)