On the computational complexity of satisfiability in propositional logics of programs |
| |
Authors: | Bogdan S Chlebus |
| |
Affiliation: | Institute of Informatics, Warsaw University, 00-901, PKiN, Warsaw, Poland |
| |
Abstract: | The satisfiability problems of propositional algorithmic logic and propositional dynamic logic are shown to be complete in the classes of languages accepted in polynomial space by the deterministic and alternating Turing machines respectively. Explicit upper and lower bounds on the space complexity are calculated. Exponential lower bounds on the space complexity of the satisfiability problems of these logics extended by adding a certain program connective are proved. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|