An undecidable problem in correspondence theory

DOI10.2307/2275473MaRDI QIDQ3984404zbMATH OpenOpenAlexFDO

Authors 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 theoryintuitionistic formulasMinsky machineundecidability of first-order definability of propositional formulas

Mathematics Subject Classification ID

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

Recommendations

• The truth about algorithmic problems in correspondence theory
• Demise of the algorithmic agenda in correspondence theory?
• scientific article; zbMATH DE number 2209455
• Undecidable problems for modal definability
• Undecidable iterative propositional calculus

Cites work

• scientific article; zbMATH DE number 4041866 (Why is no real title available?)
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines

Cited in

(22)

• Impossibility results for choice correspondences
• A codicity undecidable problem in the plane.
• Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames
• Complexity of syntactical tree fragments of independence-friendly logic
• Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi
• Undecidability of infinite Post correspondence problem for instances of size 8
• Undecidability of infinite post correspondence problem for instances of Size 9
• The truth about algorithmic problems in correspondence theory
• scientific article; zbMATH DE number 4031659 (Why is no real title available?)
• The undecidability of the disjunction property of propositional logics and other related problems
• Definability in the class of all KD45-frames -- computability and complexity
• TARSKI’S FINITE BASIS PROBLEM IS UNDECIDABLE
• Canonical formulas for K4. Part II: Cofinal subframe logics
• A dichotomy for some elementarily generated modal logics
• Deterministic SQEMA and application for pre-contact logic
• Undecidability of the Spectral Gap
• Demise of the algorithmic agenda in correspondence theory?
• Canonical varieties with no canonical axiomatisation
• scientific article; zbMATH DE number 2209455 (Why is no real title available?)
• Decidable and Undecidable Problems for First-Order Definability and Modal Definability
• Parametrized modal logic. II: The unidimensional case
• Intuitionistic epistemic logic with two modal operators

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

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