Крах алгоритмической проблематики теории соответствия?
##plugins.themes.bootstrap3.article.sidebar##
Published:
16.01.2007
##plugins.themes.bootstrap3.article.main##
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.
##plugins.generic.usageStats.downloads##
##plugins.generic.usageStats.noStats##
##plugins.themes.bootstrap3.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.