scientific article; zbMATH DE number 3880104
[For the entire collection see Zbl 0544.00022.] This paper considers some decidability problems on the loop-PDL, an extended version of propositional dynamic logic with a new formula- forming functor loop of one program variable which claims that there exists an execution sequence returning finally to the initial state. It is shown that the satisfiability problem for a loop-PDL formula is decidable in time \(\exp (n^ c)\), where n is the length of the formula and c is a constant, while its deterministic version becomes \(\Sigma^ 1_ 1\)-hard. The decidability result is established in a manner similar to \textit{R. S. Streett} [Inf. Control. 54, 121-141 (1982; Zbl 0515.68062)], while the undecidability result is obtained as a simple application of the recurring domino problem of \textit{D. Harel} [Lect. Notes Comput. Sci. 158, 177-194 (1983; Zbl 0531.68002)].
- A modal logic for cyclic repeating
- Looping vs. repeating in dynamic logic
- scientific article; zbMATH DE number 3974282 (Why is no real title available?)
- Foundations of Software Science and Computation Structures
- Derivatives on graphs for the positive calculus of relations with transitive closure
- Undecidability of the positive calculus of relations with transitive closure and difference: hypothesis elimination using graph loops
- A complete propositional dynamic logic for regular expressions with lookahead
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3345771)