Погружение интуиционистской логики в ее фрагмент от двух переменных и сложность этого фрагмента.
Article Sidebar
Опубликован:
02.11.2004
Main Article Content
Аннотация
An embedding of intuitionistic propositional logic into its two-variable fragment is constructed. Using this embedding, we prove that the decision problem for two-variable fragment of intuitionistic propositional logic is PSPACE-complete.
Скачивания
Данные скачивания пока не доступны.
Article Details
Как цитировать
Рыбаков М. Погружение интуиционистской логики в ее фрагмент от двух переменных и сложность этого фрагмента. // Логические исследования / Logical Investigations. 2004. Т. 11. C. 247-261.
Выпуск
Раздел
Статьи
Литература
Попов В.М. Погружение интуиционистского пропозиционального исчисления в его позитивны й фрагмент // Логические исследования. В ы п.8. М.: Наука, 200 3 . С. 1 5 0 -1 5 4 .
Рыбаков М.Н., Чагров Л.В. Константны е формулы в модальны х логиках: проблем а разрешения // Л огические исследования. Вып.9. М.: Наука, 2003. С. 202 -220 .
Чагров А.В. О слож ности пропозициональны х логик // С лож ностны е проблем ы м атематической логики. Калинин, 1985. С. 80 -90 .
Chagrov A., Zakharyaschev М. M odal L ogic. Oxford University Press,1997.
Garey MR., Johnson D.S Com puters and Intractability: A
Guide to the Theory o f N P -com pleteress. San Francisco, 1979. (Русский перевод: Гэри M., Джонсон Д. Вы числительные машины и труднорешаемые задачи. М.: Мир, 1982).
Halpern J. Y. The Effect of Bounding the Number of Primitive Propositions and the Depth of Nesting on the Complexity of Modal Logic // Artificial Intelligence. Vol. 75. 1995. P. 361-372.
Nishimura /. On formulas of the one variable in intuitionistic propositional calculus // The Journal of Symbolic Logic. Vol. 25. N. 1. 1960. P. 327-331.
Spaan E. Complexity of Modal Logics // PhD thesis. Department of Mathematics and Computer Science, University of Amsterdam, 1993.
Statman R. Intuitionistic propositional logic is polynomial-space complete // Theoret. Comput. Sci. Vol. 9. N. 1. 1979. P. 67-72.
Stockmeyer L. Classifying the Computational complexity of Problems // The Journal of Symbolic Logic. Vol. 52. N.l. 1987. P. 1-43. (Русский перевод: Стокмейер Л. Классификация вычислительной сложности проблем // Кибернетический сборник, вып. 26. М.: Мир, 1989. С. 20-83.)
Рыбаков М.Н., Чагров Л.В. Константны е формулы в модальны х логиках: проблем а разрешения // Л огические исследования. Вып.9. М.: Наука, 2003. С. 202 -220 .
Чагров А.В. О слож ности пропозициональны х логик // С лож ностны е проблем ы м атематической логики. Калинин, 1985. С. 80 -90 .
Chagrov A., Zakharyaschev М. M odal L ogic. Oxford University Press,1997.
Garey MR., Johnson D.S Com puters and Intractability: A
Guide to the Theory o f N P -com pleteress. San Francisco, 1979. (Русский перевод: Гэри M., Джонсон Д. Вы числительные машины и труднорешаемые задачи. М.: Мир, 1982).
Halpern J. Y. The Effect of Bounding the Number of Primitive Propositions and the Depth of Nesting on the Complexity of Modal Logic // Artificial Intelligence. Vol. 75. 1995. P. 361-372.
Nishimura /. On formulas of the one variable in intuitionistic propositional calculus // The Journal of Symbolic Logic. Vol. 25. N. 1. 1960. P. 327-331.
Spaan E. Complexity of Modal Logics // PhD thesis. Department of Mathematics and Computer Science, University of Amsterdam, 1993.
Statman R. Intuitionistic propositional logic is polynomial-space complete // Theoret. Comput. Sci. Vol. 9. N. 1. 1979. P. 67-72.
Stockmeyer L. Classifying the Computational complexity of Problems // The Journal of Symbolic Logic. Vol. 52. N.l. 1987. P. 1-43. (Русский перевод: Стокмейер Л. Классификация вычислительной сложности проблем // Кибернетический сборник, вып. 26. М.: Мир, 1989. С. 20-83.)