Document Zbl 0496.68020

On the computational complexity of satisfiability in propositional logics of programs. (English) Zbl 0496.68020

Theor. Comput. Sci. 21, 179-212 (1982).

Page: −5 −4 −3 −2 −1 ±0 +1 +2 +3 +4 +5 Show Scanned Page
scan of Zbl 0496.68020

MSC:

68Q65	Abstract data types; algebraic specification
03D15	Complexity of computation (including implicit computational complexity)
03B60	Other nonclassical logic
03B45	Modal logic (including the logic of norms)
68N01	General topics in the theory of software

Keywords:

complexity classes; nondeterminism; alternating Turing machine; satisfiability problem; propositional algorithmic logic; propositional dynamic logic

Cite Review PDF

Full Text: DOI

References:

[1]	Ben-Ari, M.; Halpern, J. Y.; Pneuli, A., Deterministic propositional dynamic logic: finite models, complexity, and completeness, MIT/LCS/TM-190 (1981)
[2]	Chandra, A. K.; Kozen, D.; Stockmeyer, L. J., Alternation, J. ACM, 28, 114-133 (1981) · Zbl 0473.68043
[3]	Chlebus, B. S., Completeness proofs for some logics of programs, Z. Math. Logik und Grundlagen Math., 28, 49-62 (1982) · Zbl 0491.03008
[4]	B.S. Chlebus, On the decidability of propositional algorithmic logic, Z. Math. Logik und Grundlagen Math.; B.S. Chlebus, On the decidability of propositional algorithmic logic, Z. Math. Logik und Grundlagen Math. · Zbl 0502.03012
[5]	Fischer, M. J.; Ladner, R. E., Propositional dynamic logic of regular programs, J. Comput. System Sci., 18, 194-211 (1979) · Zbl 0408.03014
[6]	Halpern, J. Y.; Reiff, J. H., The propositional dynamic logic of deterministic, well-structured programs, Proc. 22nd IEEE Symposium on the Foundations of Computer Science, 322-334 (1981)
[7]	Harel, D.; Meyer, A. R.; Pratt, V. R., Computability and completeness in logics of programs: preliminary report, Proc. 9th ACM Symposium on Theory of Computing, 261-268 (1977)
[8]	Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[9]	Jones, N. D., Space bounded reducibility among combinatorial problems, J. Comput. System. Sci., 11, 68-85 (1975) · Zbl 0317.02039
[10]	Kreczmar, A., Effectivity problems of algorithmic logic, (Lecture Notes in Computer Science, 14 (1974), Springer: Springer Berlin), 584-600 · Zbl 0294.68017
[11]	Meyer, A. R.; Stockmeyer, L. J., The equivalence problem for regular expressions with squaring requires exponential space, Proc. 13th Annual IEEE Symposium on Switching and Automata Theory, 125-129 (1972)
[12]	Mirkowska, G., Algorithmic logic and its applications in the theory of programs, Fund. Informat., 1, 147-165 (1977) · Zbl 0384.68010
[13]	Pratt, V. R., Semantical considerations on Floyd-Hoare logic, Proc. 17th IEEE Symposium on the Foundations of Computer Science, 109-121 (1976)
[14]	Pratt, V. R., A near optimal method for reasoning about action, J. Comput. System Sci., 20, 231-254 (1980) · Zbl 0424.03010
[15]	Salwicki, A., Formalized algorithmic languages, Bull. Acad. Pol. Sci. Ser. Math., 18, 227-232 (1970) · Zbl 0198.02801
[16]	Savitch, W. J., Relationships between nondeterministic tape complexities, J. Comput. System Sci., 4, 177-192 (1970) · Zbl 0188.33502
[17]	Seiteras, J. I.; Fischer, M. J.; Meyer, A. R., Refinements of the nondeterministic time and space hierarchies, Proc. 14th Annual IEEE Symposium on Switching and Automata Theory, 130-137 (1973)
[18]	Valiev, M. R., Decision complexity of variants of propositional dynamic logic, (Lecture Notes in Computer Science, 88 (1980), Springer: Springer Berlin), 656-664 · Zbl 0451.03003

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.