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

DOI10.2178/BSL/1122038996MaRDI QIDQ3370616zbMATH OpenOpenAlexWikidataFDO

Authors Roman Kontchakov, Agi Kurucz, Michael Zakharyaschev

Publication date 8 February 2006

Published in The 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

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

Recommendations

• Undecidability of modal and intermediate first-order logics with two individual variables
• Undecidability results on two-variable logics
• A general method for proving decidability of intuitionistic modal logics
• Undecidability results on two-variable logics
• Undecidability of modal logics of unary predicate

Cites work

• A note on the Entscheidungsproblem
• Cylindric algebras. Part II
• Decidable fragments of first-order modal logics
• Decidable fragments of first-order temporal logics
• scientific article; zbMATH DE number 1003731 (Why is no real title available?)
• scientific article; zbMATH DE number 3557754 (Why is no real title available?)
• scientific article; zbMATH DE number 755666 (Why is no real title available?)
• MIPC as the formalisation of an intuitionist concept of modality
• On languages with two variables
• On logics with two variables
• On modal logics betweenK × K × KandS5 × S5 × S5
• Representability is not decidable for finite relation algebras
• Semantical investigations in Heyting's intuitionistic logic
• The Undecidability of Monadic Modal Quantification Theory
• Undecidability of modal and intermediate first-order logics with two individual variables

Cited in

(33)

• Undecidability results on two-variable logics
• Decidability of quantified propositional intuitionistic logic and S4 on trees of height and arity \(\leq \omega\)
• Decidable and undecidable logics with a binary modality
• Correction to: ``Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter
• Complexity of finite-variable fragments of propositional temporal and modal logics of computation
• Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter
• Decidability of order-based modal logics
• Non-primitive recursive decidability of products of modal logics with expanding domains
• A general method for proving decidability of intuitionistic modal logics
• One-variable fragments of intermediate logics over linear frames
• Computational complexity of theories of a binary predicate with a small number of variables
• Simulation of two dimensions in unimodal logics
• Undecidable propositional bimodal logics and one-variable first-order linear temporal logics with counting
• Four variables suffice
• Undecidability of modal and intermediate first-order logics with two individual variables
• scientific article; zbMATH DE number 1500655 (Why is no real title available?)
• Undecidability of modal logics of unary predicate
• Modal Logics Between Propositional and First-order
• Undecidability results on two-variable logics
• Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
• Bundled fragments of first-order modal logic: (un)decidability
• Two variable fragment of term modal logic
• On the Blok-Esakia theorem
• On the Mints hierarchy in first-order intuitionistic logic
• On the Mints hierarchy in first-order intuitionistic logic
• Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино?
• A Decidable Fragment of First Order Modal Logic: Two Variable Term Modal Logic
• Decidable and Undecidable Problems for First-Order Definability and Modal Definability
• Algorithmic properties of modal and superintuitionistic logics of monadic predicates over finite Kripke frames
• Variations on the Kripke trick
• Strictly positive fragments of the provability logic of Heyting arithmetic
• Superintuitionistic predicate logics of linear Kripke frames: undecidability with two individual variables
• Non-axiomatizability of modal predicate logics of Dedekind-complete linear orders with constant domains

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3370616)