Abstract
The problem of whether an arbitrary formula of Propositional Dynamic Logic (PDL) is deducible from a fixed axiom scheme of PDL is Π 11 -complete. This contrasts with the decidability of the problem when the axiom scheme is replaced by any single PDL formula.
This research was supported in part by the National Science Foundation, grant nos. MCS 7719754, MCS 8010707, and MCS 7910261, and by a grant to the MIT Laboratory for Computer Science by the IBM Corporation.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Fischer, M. J. and R. E. Ladner, "Propositional Dynamic Logic of Regular Programs", JCSS, 18, 194–211, 1979.
Mirkowska, G., "Complete Axiomatization of Algorithmic Properties of Program Schemes with Bounded Nondeterministic Interpretations", Proceedings of the 12th ACM Symposium on Theory of Computing, 14–21, 1980.
Mirkowska, G., personal communication. Warsaw, July, 1980.
Pratt, V. R., "Models of Program Logics", JCSS, 20, 231–254, 1980.
Rogers, H., Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Company, 1967.
Shoenfield, J. R., Mathematical Logic, Addison-Wesley Publishing Company, 1967.
Streett, R. S., "Propositional Dynamic Logic of Looping and Converse", Proceedings of the 13th ACM Symposium on Theory of Computing, 1981.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1981 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Meyer, A.R., Streett, R.S., Mirkowska, G. (1981). The deducibility problem in Propositional Dynamic Logic. In: Even, S., Kariv, O. (eds) Automata, Languages and Programming. ICALP 1981. Lecture Notes in Computer Science, vol 115. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-10843-2_20
Download citation
DOI: https://doi.org/10.1007/3-540-10843-2_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-10843-6
Online ISBN: 978-3-540-38745-9
eBook Packages: Springer Book Archive