scientific article; zbMATH DE number 3880104

From MaRDI portal
Publication:3345771





[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)].











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)