The complexity of propositional tense logics. (English) Zbl 0831.03005

Rijke, Maarten de (ed.), Diamonds and defaults. Studies in pure and applied intensional logic. Papers presented at a seminar on intensional logic held at the University of Amsterdam, Netherlands during the period September 1990-May 1991. Dordrecht: Kluwer Academic Publishers. Synth. Libr. 229, 287-307 (1993).
Results on complexity are (non-trivially) transferred from propositional modal logics to propositional tense logics. Namely, it is proved that satisfiability in the tense systems \(K_t\), \(T_t\), \(K4_t\), \(S4_t\) is PSPACE-complete.
For the entire collection see [Zbl 0812.00020].


03B45 Modal logic (including the logic of norms)
03D15 Complexity of computation (including implicit computational complexity)
68Q25 Analysis of algorithms and problem complexity