**Now Playing:**REPOSTED

**Topic:**

**GENERAL LOGIC**

## Decidability of Quantified Propositional Intuitionistic Logic and S4 on Trees of Height and Arity [le] [omega]

By Richard Zach

Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers [forall] p,[exist] 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 modalS4and some G?del-Dummett logics with quantifiers over propositions.

Source: Journal of Philosophical Logic

link 1

link 2

Posted by Tony Marmo
at 00:01 GMT

Updated: Thursday, 6 January 2005 18:51 GMT