Process logic
Vaughan Pratt · ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL) · 1979
We discuss problems arising in reasoning about on-going processes, using the modal constructs after, throughout, during, and preserves. Earlier work established decidability of the theory whose language included only the first two of these, along with program connectives | , ; and *. Here we give a complete Gentzen-type axiomatizations for useful combinations of the other modalities. We also indicate how such Gentzen-type axiomatizations lead to deterministic exponential time upper bounds on the complexity of decision procedures for these languages. It remains an open problem how to completely axiomatize the combination of modalities during and preserves.
Cited by 76 works. doi:10.1145/567752.567761 Open-access PDF
Authors
References
- A Discipline of Programming
- The temporal logic of programs
- Untersuchungen �ber das logische Schlie�en. I
- 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
- A near-optimal method for reasoning about action
- 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.
- Nondeterminism in logics of programs
- A practical decision method for propositional dynamic logic (Preliminary Report)
- An introduction to algorithmic logic. Metamathematical investigations in the theory of programs