zbMATH — the first resource for mathematics

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