Крах алгоритмической проблематики теории соответствия?
Article Sidebar
Published:
16.01.2007
Main Article Content
Abstract
Three key problems of the Correspondence Theory are considered: given a modal propositional formula and a first-order formula, to recognize, whether they are equivalent in Kripke frames (the correspondence problem); given a modal propositional formula, to recognize, whether there is a first-order formula which is equivalent to it in Kripke frames (the problem of first-order definability of modal propositional formulas), given a first-order formula, to recognize, whether there is a modal propositional formula which is equivalent to it in Kripke frames (the problem of modal definability of first-order formulas). For all of these problems concise proofs of algorithmic undecidability have been given.
Downloads
Download data is not yet available.
Article Details
How to Cite
Chagrov A., Chagrova L. Крах алгоритмической проблематики теории соответствия? // Logicheskie Issledovaniya / Logical Investigations. 2007. VOL. 13. C. 248-272.
Issue
Section
Papers
References
Мальцев А.И., Алгоритмы и рекурсивные функции. М.: Наука, 1986.
Фейс Р. Модальная логика. М.: Наука, 1974.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости // Алгебра и логика. 1990. Т. 29. N 3. С. 350-367.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости. II // Алгебра и логика. 1990. Т. 29. N 5. С. 613-623.
Чагров А.В. Алгоритмическая проблема аксиоматизации табличной нормальной модальной логики // Логические исследования. Вып 9. М.: Наука, 2002. C. 251-263.
Чагрова Л.А. О проблеме определимости пропозициональных формул интуиционистской логики формулами классической логики первого порядка. Калинин: КГУ, 1989. (Диссертация на соискание ученой степени кандидата физико-математических наук, защищенная в Институте математики с вычислительным центром АН МССР, Кишинев.)
van Benthem J.A.F.K. Modal Logic and Classical Logic. Bibliopolis, Napoli, 1983.
van Benthem J.A.F.K. Correspondence Theory // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition, Vol. 3. Kluwer Academic Publishers, 2001. P. 325-408.
Chagrov A.V., Chagrova L.A. Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames // Studia Logica. 1995. Vol. 55. No. 3. P. 421-448.
Chagrov A.V., Chagrova L.A. The Truth About Algorithmic Problems in Correspondence Theory // Advances in Modal Logic. Vol. 6. College Publications, 2006. P. 121-138.
Chagrov A., Zakharyashchev M. The undecidability of the disjunction property of propositional logics and other related problems // Journal of Symbolic Logic. 1993. Vol. 58. P. 967-1002.
Chagrov A., Zakharyashchev M. Modal Logic. Oxford University Press, 1997.
Chagrova L.A. An undecidable problem in correspondence theory // Journal of Symbolic Logic. 1991. Vol. 56. P. 1261-1272.
Isard S. A finitely axiomatizable undecidable extension of К // Theoria. 1977. Vol. 43. P. 195-202.
Kripke S. Semantical analysis of modal logic, Part I // Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik. 1963. Bd. 9. S. 67-96.
Zakharyaschev M., Wolter F. and Chagrov A. Advanced Modal Logic // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition. Vol. 3. Kluwer Academic Publishers, 2001. P. 83-266.
Фейс Р. Модальная логика. М.: Наука, 1974.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости // Алгебра и логика. 1990. Т. 29. N 3. С. 350-367.
Чагров А.В. Неразрешимые свойства расширений логики доказуемости. II // Алгебра и логика. 1990. Т. 29. N 5. С. 613-623.
Чагров А.В. Алгоритмическая проблема аксиоматизации табличной нормальной модальной логики // Логические исследования. Вып 9. М.: Наука, 2002. C. 251-263.
Чагрова Л.А. О проблеме определимости пропозициональных формул интуиционистской логики формулами классической логики первого порядка. Калинин: КГУ, 1989. (Диссертация на соискание ученой степени кандидата физико-математических наук, защищенная в Институте математики с вычислительным центром АН МССР, Кишинев.)
van Benthem J.A.F.K. Modal Logic and Classical Logic. Bibliopolis, Napoli, 1983.
van Benthem J.A.F.K. Correspondence Theory // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition, Vol. 3. Kluwer Academic Publishers, 2001. P. 325-408.
Chagrov A.V., Chagrova L.A. Algorithmic problems concerning first-order definability of modal formulas on the class of all finite frames // Studia Logica. 1995. Vol. 55. No. 3. P. 421-448.
Chagrov A.V., Chagrova L.A. The Truth About Algorithmic Problems in Correspondence Theory // Advances in Modal Logic. Vol. 6. College Publications, 2006. P. 121-138.
Chagrov A., Zakharyashchev M. The undecidability of the disjunction property of propositional logics and other related problems // Journal of Symbolic Logic. 1993. Vol. 58. P. 967-1002.
Chagrov A., Zakharyashchev M. Modal Logic. Oxford University Press, 1997.
Chagrova L.A. An undecidable problem in correspondence theory // Journal of Symbolic Logic. 1991. Vol. 56. P. 1261-1272.
Isard S. A finitely axiomatizable undecidable extension of К // Theoria. 1977. Vol. 43. P. 195-202.
Kripke S. Semantical analysis of modal logic, Part I // Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik. 1963. Bd. 9. S. 67-96.
Zakharyaschev M., Wolter F. and Chagrov A. Advanced Modal Logic // D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd Edition. Vol. 3. Kluwer Academic Publishers, 2001. P. 83-266.