Propositional dynamic logic with recursive programs

Several promising, recent research directions can be mentioned. One of them is motivated by the need of analyzing distributed recursive programs, and aims at identifying reasonabl Documents: Advanced Search Include Citations. Authors: Advanced Search Include Citations. We develop a general framework for the design of temporal logics for concurrent recursive programs. A program execution is modeled as a partial order with multiple nesting relations. To specify properties of executions, we consider any temporal logic whose modalities aredefinable in monadi To specify properties of executions, we consider any temporal logic whose modalities aredefinable in monadic second-order logic and that, in addition, allows PDL-like path expressions.

This captures, in a unifying framework, a wide range of logics defined for ranked and unranked trees, nested words, and Mazurkiewicz traces that have been studied separately. This paper presents Smyle, a tool for synthesizing asynchronous and distributed implementation models from sets of scenarios that are given as message sequence charts MSCs.

The latter specify desired or unwanted behavior of the system to be. Provided with such positive and negative example scenari Abstract - Cited by 4 1 self - Add to MetaCart This paper presents Smyle, a tool for synthesizing asynchronous and distributed implementation models from sets of scenarios that are given as message sequence charts MSCs. Provided with such positive and negative example scenarios, Smyle employs dedicated learning techniques and propositional dynamic logic PDL over MSCs to generate a system model that conforms with the given examples.

We will present some of them in section 4 , providing some pointers regarding their relative expressivity, their axiomatizations, and their computational complexity. We present the syntax and semantics of PDL in section 2. The proof theory of PDL is presented in section 2.

We address the problem of decidability and complexity in section 2. Propositional dynamic logic PDL is designed for representing and reasoning about propositional properties of programs. Complex formulas and complex programs over this base are defined as follows:. More formally:. Finally, we adopt the standard rules for omission of parentheses. Formulas can be used to describe the properties that hold after the successful execution of a program. Semantically speaking, formulas are interpreted by sets of states and programs are interpreted by binary relations over states in a transition system.

We have for instance:. Now consider a formula A. Some remarkable formulas of PDL are valid. The reader may try to prove them formally, or at least start convincing themselves on the few examples displayed above. The behavior of a system described as an LTS is indeed often slightly hidden in its form. For instance, on simple inspection, it is easy to convince oneself that the two LTSs depicted above have the same behavior, and satisfy the same PDL formulas.

To finish this section on syntax and semantics we give the theoretical foundation of these claims. Given two LTSs, one may ask whether they satisfy the same formulas. The notion of bisimulation has become the standard measure for equivalence of Kripke models and Labeled Transition Systems. We say that two LTSs are bisimilar when there exists a bisimulation between them. Hence one can simply compare the behaviors of two LTSs by inspecting solely the atomic programs and safely extrapolate on the comparative behavior of these LTSs even for complex programs.

We say that the program constructs of PDL are safe for bisimulation. See Van Benthem [] for precise characterizations of program constructs that are safe for bisimulation. It is readily seen that the two instances of LTSs above are bisimilar.

The states x 1 and y 1 satisfy exactly the same PDL formulas. So do the states x 1 and y 2 , etc. Of course, PDL is an extension of classical propositional logic.

We first expect that all propositional tautologies hold, and all propositional reasoning is allowed. Thus, PDL contains every instance of the familiar distribution axiom schema:.

A modal logic is normal if it obeys A0 and N. Finally, PDL is the least normal modal logic containing every instance of the following axiom schemas. It is easy to establish that I can be replaced by the following axiom schema induction axiom schema :.

Soon, Parikh came up with a proof, too. Kozen and Parikh []. Different alternative proof theories of PDL have also been sought after. Even early on, notably in Pratt []. Let us then also mention the completeness of related theories by Nishimura [] and Vakarelov []. An alternative formulation of a deducibility predicate for PDL permits the use of an infinitary rule of inference, as for instance in Goldblatt [a].

An infinitary rule of inference takes an infinite number of premises. The aim of the complexity theory is to establish the computability of the property sat A in terms of resources of time or space.

The complexity of a logic L is often identified with the problem of deciding the satisfiability of its formulas, defined as:. The complete axiomatization of PDL is a recursive definition of the set of valid PDL formulas, or in other words, of the set of formulas whose negation is not satisfiable. It would run forever, and one could not be sure about it at any time. But there is a way out of this uncertainty.

The finite model property offers a basis for a sub-procedure SP2 that consists in enumerating one by one the finite models of PDL and testing whether one of them satisfies the formula. Symmetrically to the first sub-procedure SP1 , if the formula A is not satisfiable, then SP2 will never find a model satisfying it, it will run forever, and one could not be sure about it at any time.

The procedure halts when either SP1 or SP2 provides an answer. If the procedure that is obtained is sufficient to conclude that the problem PDL-SAT is decidable, it is very ineffective in practice. There is a result—due to Fischer and Ladner [] and Kozen and Parikh []— stronger than the finite model property, that is small model property :.

This means that we would now know when to stop looking for a model satisfying a formula in the procedure SP2. Hence, we can use SP2 to test whether a formula is satisfiable, but once we have exhausted all small models, we can conclude that the formula is not satisfiable. This yields a procedure that runs non-deterministically in exponential time NEXPTIME : guess a model of size at most singly exponential, and check whether it satisfies the formula.

Observing that a formula of PDL can efficiently describe the computation of a linear-space—bounded alternating Turing machine, Fischer and Ladner [] first established the lower bound of exponential time of PDL-SAT.

An algorithm more efficient in practice, although still running in deterministic exponential time in the worst case, is proposed in De Giacomo and Massacci []. Historically, logics of programs stem from the work in the late s of computer scientists interested in assigning meaning to programming languages and finding a rigorous standard for proofs about the programs.

For example such proofs may be about the correctness of a program with respect to an expected behavior, or about the termination of a program.

A seminal paper is Floyd [] which presents an analysis of the properties of structured computer programs using flowcharts. Some early work such as Yanov [] or Engeler [] had advanced and studied formal languages in which the properties of program connectives can be expressed.

The formalism of Hoare [] was a milestone in the advent of PDL. We often talk about Hoare logic, or Floyd-Hoare logic, or Hoare calculus when referring to this formalism. It was true some decades ago, and it is still the case: validating a program is more often than not done by testing it on a reasonable variety of inputs.

If eventually for every tested input we obtain the expected output, one has a reasonable belief that the program has no error. However, this is a time consuming method of validation, and it leaves place for untested inputs that would fail.

Finding these errors after the program has been implemented and gone into use is even more costly in resources. Reasoning about program correctness with formal methods is crucial for critical systems since it offers a way of proving exhaustively that a program has no errors. To illustrate the sort of principles of programs captured by the rules in the Hoare calculus it is enough to consult some of them.

The rule of composition captures the elementary sequential composition of programs. The rule of iteration is an important one because it captures the essential ability of programs to execute some portion of code repeatedly until a certain condition ceases to hold. Finally, the two rules of consequence are fundamental to give a formal basis to intuitively clear reasoning involving weaker post-conditions and stronger preconditions respectively.

From the formalism presented in Hoare [], we leave out its axiom schemas as it would require a first-order language. Finally, in subsequent work on Hoare logic, more rules are also often added. See Apt [] for an early overview. In addition, important programming constructs are easily introduced in PDL by definitional abbreviation:.

Thus, it seems that with PDL we are well-equipped to logically prove the correctness of structured programs. Beyond this rather hand-waving connection between PDL and Hoare calculus, perhaps it is not yet clear how they relate formally.

PDL is in fact a generalization of Hoare calculus in the sense that all the rules of the Hoare calculus can be proven in the axiomatic system of PDL.

Rigorously, the Hoare calculus contains axioms that would require the extended language of first-order Dynamic Logic. This is quite remarkable, so we will show here the two above rules to serve as examples. The proofs start by assuming the premises of the rules.

Then by using these assumptions, axioms and rules of PDL, and nothing else, the objective is to establish that the conclusion of the rules logically follows. In the context of PDL, the two rules of consequence are in fact special cases of the rule of composition. Particularly, it only allows one to reason about partial correctness.

That is, a partially correct program may have non-terminating executions. Once Bi has reached its accepting state it remains there forever. Note that the size of Bi is linear in the size of Ai. Furthermore, Bi can be constructed such that it is complete because every run that reaches an accepting state never stops. Taking the union of these Vpas one obtains a reachability Vpa B for Lbox.

Lemma 3. Diamond automaton. We give an informal description of the diamond au- tomaton. This automaton is designed to accept trees that satisfy both the dia- mond condition and the one of Definition 2. At the beginning no formula is checked. The diamond automaton reads the labelling t x of the current node x. If it contains some diamond formula, it will go for each of these formulas in a different branch of the tree where it checks this formula.

If the automaton was already checking for a diamond formula, it keeps looking for its validation by choosing yet another branch. As the tree should satisfy the unique diamond path property, a validation of the diamond formulas can be found in this way. For this it stores in its control state the current state q of A in the simulation and uses its stack to mimic the one of A.

If this symbol is popped later, then it is recorded in the state of the Vpta that the simulation is at the bottom of the stack, i. In this case the Vpta signals this successful simulation in the next transition by setting a special flag in all successor states.

This flag also defines the acceptance condition. If the flag is set infinitely often on each path, then the input is accepted. For this to work we also set the flag if no simulation is performed. Lemma 4. Now, consider the automaton obtained by taking the product of the local automaton, the box automaton, and the diamond automaton. Lemma 5. Using Theorem 3 we deduce the decidability of the satisfiability problem for recursive PDL formulas.

Theorem 4. Given a recursive PDL formula, one can decide in doubly expo- nential time whether it is satisfiable. We leave open the question whether this complexity is optimal. A singly expo- nential lower bound directly follows from the one for standard PDL [5].

The meaning of such a formula is that there exists a path that is accepted by A. For the semantics we only give the definitions for the new constructs.

One easily shows that adapted versions of Propositions 1, 2, and 3 still hold. All this results in the following lemma. Lemma 6. Finally, one has to check emptiness for a stair parity Vpta, which can be done in exponential time Theorem 3. Theorem 5. Again, we leave open the question whether this complexity is optimal. The result on the satisfiability of this logic subsumes all known decidable extensions of PDL with context-free programs. Another possible direction for future research is to combine visibly pushdown automata with the game logic of Parikh [12].

References 1. Alur, S. Chaudhuri, and P. A fixpoint calculus for local and global program flows. To appear. Alur, K.

Etessami, and P. A temporal logic of nested calls and returns. Springer, Alur and P. Visibly pushdown languages. ACM, Nondeterministic propositional dynamic logic with intersection is decidable. Fischer and R. Propositional dyncamic logic of regular programs. Journal of Computer and System Sciences, 18 2 —, Harel and M. Strengthened results on nonregular PDL. Harel, D. Kozen, and J. Dynamic Logic. Foundations of Computing. MIT Press, Harel and D. Deciding properties of nonregular programs.

Harel and E. More on nonregular PDL: Expressive power, finite models, fibonacci programs. Madhusudan, and O. Visibly pushdown games. PDL with intersection and converse is decidable. The logic of games an its applications. Annals of discrete mathematics, —, Theoretical Computer Science, —, Propositional dynamic logic of looping and converse is elementary decidable. Information and Control, —, Languages, automata, and logic.

Vardi and P.