Abstract. The p-calculus can be viewed as essentially the "ultimate" program logic, as it expressively subsumes all propositional program logics, including dynamic logics, process logics, and temporal logics. It is known that the satisfiability problem for the p-calculus is EXPTIMEcomplete. This upper bound, however, is known for a version of the logic that has only forward modalities, which express weakest preconditions, but not backward modalities, which express strongest postconditions. Our main result in this paper is an exponential time upper bound for the satisfiability problem of the p-calculus with both forward and backward modalities. To get this result we develop a theory of two-way alternating automata on infinite trees.
The satisfiability problem for the general μ-calculus with converse modalities (MC) is known to be EXPTIME-complete REF ].
Reasoning about The Past with Two-Way Automata
In 25th International Colloqium on Automata, Languages and Programming, ICALP ’98
Computer Science