Undecidability of First-Order Intuitionistic and Modal Logics with Two variables

DOI10.2178/bsl/1122038996zbMath1096.03008OpenAlexW2057232741WikidataQ62048648 ScholiaQ62048648MaRDI QIDQ3370616

Roman Kontchakov, Agi Kurucz, Michael Zakharyashchev

Publication date: 8 February 2006

Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.298.6638

zbMATH Keywords

decidabilitymonadic two-variable fragmentstwo-variable fragment of first-order intuitionistic logictwo-variable fragment of quantified modal logic

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (12)

Decidability of order-based modal logics ⋮ Undecidability of QLTL and QCTL with two variables and one monadic predicate letter ⋮ Complexity of finite-variable fragments of propositional temporal and modal logics of computation ⋮ One-variable fragments of intermediate logics over linear frames ⋮ Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино? ⋮ A Decidable Fragment of First Order Modal Logic: Two Variable Term Modal Logic ⋮ Computational complexity of theories of a binary predicate with a small number of variables ⋮ Unnamed Item ⋮ Non-primitive recursive decidability of products of modal logics with expanding domains ⋮ Unnamed Item ⋮ Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter ⋮ On the Blok-Esakia Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cylindric algebras. Part II
• Semantical investigations in Heyting's intuitionistic logic
• Decidable fragments of first-order temporal logics
• On logics with two variables
• Representability is not decidable for finite relation algebras
• Decidable fragments of first-order modal logics
• The Undecidability of Monadic Modal Quantification Theory
• On languages with two variables
• Undecidability of modal and intermediate first-order logics with two individual variables
• On modal logics betweenK × K × KandS5 × S5 × S5
• MIPC as the formalisation of an intuitionist concept of modality
• A note on the Entscheidungsproblem

This page was built for publication: Undecidability of First-Order Intuitionistic and Modal Logics with Two variables