An undecidable problem in correspondence theory

DOI10.2307/2275473zbMath0737.03018OpenAlexW2144185328MaRDI QIDQ3984404

L.A.Chagrova

Publication date: 27 June 1992

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

Full work available at URL: https://doi.org/10.2307/2275473

zbMATH Keywords

correspondence theoryMinsky machineintuitionistic formulasundecidability of first-order definability of propositional formulas

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Undecidability and degrees of sets of sentences (03D35) Automata and formal grammars in connection with logical questions (03D05) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (10)

The undecidability of the disjunction property of propositional logics and other related problems ⋮ Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames ⋮ Definability in the class of all -frames – computability and complexity ⋮ Unnamed Item ⋮ Canonical formulas for K4. Part II: Cofinal subframe logics ⋮ A dichotomy for some elementarily generated modal logics ⋮ Complexity of syntactical tree fragments of independence-friendly logic ⋮ Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi ⋮ Negation and partial axiomatizations of dependence and independence logic revisited ⋮ Canonical varieties with no canonical axiomatisation

Cites Work

• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Unnamed Item

This page was built for publication: An undecidable problem in correspondence theory