Decidability of quantified propositional intuitionistic logic and s4 on trees of height and arity ≤ω
Graduate studies at Western
Journal of Philosophical Logic 33 (2):155-164 (2004)
|Abstract||Quantified propositional intuitionistic logic is obtained from propositional intuitionistic logic by adding quantifiers ∀p, ∃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 ω, 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|
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev (2005). Undecidability of First-Order Intuitionistic and Modal Logics with Two Variables. Bulletin of Symbolic Logic 11 (3):428-438.
Peter W. O'Hearn & David J. Pym (1999). The Logic of Bunched Implications. Bulletin of Symbolic Logic 5 (2):215-244.
Tomasz Połacik (1994). Second Order Propositional Operators Over Cantor Space. Studia Logica 53 (1):93 - 105.
David Ellerman (2010). The Logic of Partitions: Introduction to the Dual of the Logic of Subsets. Review of Symbolic Logic 3 (2):287-350.
Morten H. Sørensen & Paweł Urzyczyn (2010). A Syntactic Embedding of Predicate Logic Into Second-Order Propositional Logic. Notre Dame Journal of Formal Logic 51 (4):457-473.
Aldo Ursini (1979). A Modal Calculus Analogous to K4w, Based on Intuitionistic Propositional Logic, Iℴ. Studia Logica 38 (3):297 - 311.
Mitsuhiro Okada (1987). A Weak Intuitionistic Propositional Logic with Purely Constructive Implication. Studia Logica 46 (4):371 - 382.
Milan Božić & Kosta Došen (1984). Models for Normal Intuitionistic Modal Logics. Studia Logica 43 (3):217 - 245.
Marta Bílková (2007). Uniform Interpolation and Propositional Quantifiers in Modal Logics. Studia Logica 85 (1):1 - 31.
Philip Kremer (1997). On the Complexity of Propositional Quantification in Intuitionistic Logic. Journal of Symbolic Logic 62 (2):529-544.
Added to index2009-01-28
Total downloads8 ( #131,747 of 732,277 )
Recent downloads (6 months)0
How can I increase my downloads?