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 modal S4 and 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
