Константные формулы в модальных логиках: проблема разрешения.
Article Sidebar
Опубликован:
03.10.2002
Main Article Content
Аннотация
The main result: the provability problem of constant formulas is VS?ACE-complete for modal logics К , K4. Some closed questions are discussed.
Скачивания
Данные скачивания пока не доступны.
Article Details
Как цитировать
Рыбаков М., Чагров А. Константные формулы в модальных логиках: проблема разрешения. // Логические исследования / Logical Investigations. 2002. Т. 9. C. 202-220.
Выпуск
Раздел
Статьи
Литература
Чагров А. В. Логика, не являющаяся ни конечно-значной, ни бесконечно-значной // Труды научно-исследовательского семинара Логического центра Института философии РАН. Вып. XIV. М., 2000. С. 59-67.
Чагров А. В. О сложности пропозициональных логик // Сложностные проблемы математической логики. Калинин: КГУ, 1985. С. 80-90.
Семантика модальных и интенсиональных логик. Сб. статей. Пер. с англ., сост., общ. ред. и вступит, статья В.А.Смирнова. М.:Прогресс, 1981.
Chagrov A., Zakharvaschev М. Modal Logic. Oxford University Press, 1997. 605 p.
Garey M.R. and Johnson D.S. Computers and Intractability” A Guide to the Theory of NP-completeness. San Francisco. 1979. (Русский перевод: Гэри М. и Джонсон Д. Вычислительные машины и труднорешаемые задачи. М , Мир. 1982.)
Halpern J.Y. The Effect of Bounding the Number of Primiti ve Propositions and the Depth of Nesting on the Complexity of Modal Logic // Artificial Intelligence. 1995. Vol. 75. No. 2. P. 361-372.
Ladner R.E. The computational complexity of provability in systems of modal logic // SIAM Journal on Computing. 1977. Vol. 6. P. 467--480.
Nishimura I. On formulas of the one variable in intuitionistic propositional calculus // The Journal of Symbolic Logic. Vol. 25 (1960). No. 1. P. 327-331.
Statman R. Intuitionistic propositional logic is polynomial-space complete // Theoret. Comput. Sci. Vol. 9 (1979). No. 1. P. 67-72. 10 .Stockmeyer L. Classifying the Computational complexity of Problems 11The Journal of Symbolic Logic. Vol. 52 (1987), No. 1. P.1-43. (Русский перевод: Л. Стокмейер. Классификация вычислительной сложности проблем // Кибернетический сборник. Вып. 26. М.: Мир, 1989. С. 20-83.) Zakharyaschev М., Wolter F., and Chagrov A. Advanced Modal Logic 11 D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd ed. Vol. 3. Kluver Academic Publishers, 2001. P. 83-266.
Чагров А. В. О сложности пропозициональных логик // Сложностные проблемы математической логики. Калинин: КГУ, 1985. С. 80-90.
Семантика модальных и интенсиональных логик. Сб. статей. Пер. с англ., сост., общ. ред. и вступит, статья В.А.Смирнова. М.:Прогресс, 1981.
Chagrov A., Zakharvaschev М. Modal Logic. Oxford University Press, 1997. 605 p.
Garey M.R. and Johnson D.S. Computers and Intractability” A Guide to the Theory of NP-completeness. San Francisco. 1979. (Русский перевод: Гэри М. и Джонсон Д. Вычислительные машины и труднорешаемые задачи. М , Мир. 1982.)
Halpern J.Y. The Effect of Bounding the Number of Primiti ve Propositions and the Depth of Nesting on the Complexity of Modal Logic // Artificial Intelligence. 1995. Vol. 75. No. 2. P. 361-372.
Ladner R.E. The computational complexity of provability in systems of modal logic // SIAM Journal on Computing. 1977. Vol. 6. P. 467--480.
Nishimura I. On formulas of the one variable in intuitionistic propositional calculus // The Journal of Symbolic Logic. Vol. 25 (1960). No. 1. P. 327-331.
Statman R. Intuitionistic propositional logic is polynomial-space complete // Theoret. Comput. Sci. Vol. 9 (1979). No. 1. P. 67-72. 10 .Stockmeyer L. Classifying the Computational complexity of Problems 11The Journal of Symbolic Logic. Vol. 52 (1987), No. 1. P.1-43. (Русский перевод: Л. Стокмейер. Классификация вычислительной сложности проблем // Кибернетический сборник. Вып. 26. М.: Мир, 1989. С. 20-83.) Zakharyaschev М., Wolter F., and Chagrov A. Advanced Modal Logic 11 D.M. Gabbay, F. Guenthner (eds.). Handbook of Philosophical Logic. 2nd ed. Vol. 3. Kluver Academic Publishers, 2001. P. 83-266.