# Decidability of quantified propositional intuitionistic logic and S4 on trees of height and arity ≤ ω

Zach, Richard. 2004. “Decidability of Quantified Propositional Intuitionistic Logic and S4 on Trees of Height and Arity ≤ω.” Journal of Philosophical Logic 33 (2): 155–64. https://doi.org/10.1023/B:LOGI.0000021744.10237.d0.

Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers $$\forall p$$, $$\exists p$$, where the propositional variables range over upward-closed subsets of the set of worlds in a Kripke structure. If the permitted accessibility relations are arbitrary partial orders, the resulting logic is known to be recursively isomorphic to full second-order logic (Kremer, 1997). It is shown that if the Kripke structures are restricted to trees of at height and width at most $$\omega$$, the resulting logics are decidable. This provides a partial answer to a question by Kremer. The result also transfers to modal S4 and some Gödel-Dummett logics with quantifiers over propositions.

Review: M. Yasuhara (Zentralblatt 1054.03011)