Four variables suffice

MaRDI QIDQ3629230zbMATH OpenFDO

Authors Alasdair Urquhart

Publication date 27 May 2009

zbMATH Keywords

decidabilityfragments of relevant propositional logicsundecidability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Undecidability of modal and intermediate first-order logics with two individual variables
• Relevance logic: problems open and closed
• The undecidability of entailment and relevant implication
• Undecidability of First-Order Intuitionistic and Modal Logics with Two variables
• Complexity of intuitionistic and Visser's basic and formal logics in finitely many variables

Cited in

(5)

• Extracting \(\mathsf{BB'IW}\) inhabitants of simple types from proofs in the sequent calculus \(LT_\to^t\) for implicational ticket entailment
• Current trends in substructural logics
• A Logical Autobiography
• Бинарный предикат, транзитивное замыкание, две-три переменные: сыграем в домино?
• Four states are enough!

This page was built for publication: Four variables suffice

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