A practical decision method for propositional dynamic logic (Preliminary Report)
Vaughan Pratt · ACM Symposium on Theory of Computing (STOC) · 1978
We give a new characterization of the set of satisfiable formulae of propositional dynamic logic (PDL) based on the method of tableaux. From it we derive a heuristically efficient goal-directed proof procedure and a complete axiom system for PDL. The proof procedure illustrates a striking connection between natural deduction and symbolic execution. The completeness proof for the axiom system incorporates a method for the automatic synthesis of invariants. We also augment DL with new modalities throughout, during, and preserves, supply a new semantic foundation for DL programs, and show how to extend the satisfiability characterizations for PDL to throughout.
Cited by 89 works. doi:10.1145/800133.804362
Authors
References
- A Discipline of Programming
- Guarded commands, nondeterminacy and formal derivation of programs
- Untersuchungen �ber das logische Schlie�en. I
- Semantical Analysis of Modal Logic I Normal Modal Propositional Calculi
- First-Order Logic
- Vaughan R. Pratt. Semantical considerations on Floyd–Hoare logic. 17th Annual Symposium on Foundations of Computer Science, Institute of Electrical and Electronics Engineers, New York1976, pp. 109–121. - Michael J. Fischer and Richard E. Ladner. Propositional dynamic logic of regular programs. Journal of computer and system sciences, vol. 18 (1979), pp. 194–211. - Krister Segerberg. A completeness theorem in the modal logic of programs. Universal algebra and applications. Papers presented at Stefan Banach International Mathematical Center at the semester “Universal algebra and applications” held February 15–June 9, 1978, edited by Tadeuz Traczyk, Banach Center Publications, vol. 9, PWN—Polish Scientific Publishers, Warsaw1982, pp. 31–46. - Rohit Parikh. The completeness of propositional dynamic logic. Mathematical foundations of computer science 1978, Proceedings, 7th symposium, Zakopane, Poland, September 4–8, 1978, edited by J. Winkowski, Lecture notes in computer science, vol. 64, Springer-Verlag, Berlin, Heidelberg, and New York, 1978, pp. 403–415. - Dexter Kozen and Rohit Parikh. An elementary proof of the completeness of PDL. Theoretical computer science, vol. 14(1981), pp. 113–118.
- Propositional modal logic of programs
- On the theory of programming logics
- The synthesis of loop predicates
- A. Salwicki. Formalized algorithmic languages. English with English and Russian summaries. Bulletin de l'Académie Polonaise des Sciences, Série des sciences mathématiques, astronomiques et physiques, vol. 18 (1970), pp. 227–232, XVII, XVII. - A. Salwicki. On the equivalence of FS-expressions and programs. English with English and Russian summaries. Bulletin de l'Académie Polonaise des Sciences, Série des sciences mathématiques, astronomiques et physiques, vol. 18 (1970), pp. 275–278, XXI, XXI. - A. Salwicki. On the predicate calculi with iteration quantifiers. English with English and Russian summaries. Bulletin de l'Académie Polonaise des Sciences, Série des sciences mathématiques, astronomiques et physiques, vol. 18 (1970), pp. 279–285, XXI, XXI.