Сложность проблемы разрешения базисной и формальной логик.
Article Sidebar
Опубликован:
04.11.2003
Main Article Content
Аннотация
The complexity o f decision problem for basic, proposition logic BPL and formal proposition logic FPL is considered. It is proved that decision problem for positive fragments o f both BPL and FPL is PSPACE-complete. The main result is that decision problem for variable-free fragment o f BPL and one-variable fragment o f FPL is PSP ACE-complete.
Скачивания
Данные скачивания пока не доступны.
Article Details
Как цитировать
Рыбаков М. Сложность проблемы разрешения базисной и формальной логик. // Логические исследования / Logical Investigations. 2003. Т. 10. C. 158-166.
Выпуск
Раздел
Статьи
Литература
Рыбаков М.Н ., Чагров А.В. Константные формулы в модальных логиках: проблема разрешения // Логические исследования. Вып.9. М : Наука, 2003.
Рыбаков М.Н., Чагров А.В. Модальные формулы без переменных и PSPACE-полнота // Современная логика: Проблемы теории, истории и применения в науке. Материалы VII Международной научной конференции. СПб: Издательство Санкт-Петербургского университета. 2002. С. 498-500.
Рыбаков М.Н., Чагров А. В. О сложности модальных логик, имеющих доказуемостную интерпретацию, с ограничениями на число переменных // Колмогоров и современная математика. Международная конференция. М.: Издательство МГУ, 2003. С. 707-708.
Семантика модальных и интенсиональных логик // Пер. с англ., сост., общ. ред. и вступит, статья В.А. Смирнова. М.: Прогресс, 1981.
Chagrov A., Zakharyaschev М. Modal Logic. Oxford University Press, 1997.
Garey M.R.., Johnson D.S. Computers and Intractability: A Guide to the Theory o f NP-completeness. San Francisco, 1979. (Русский перевод: Гэри M , Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982).
Halpern J. Y. The Effect o f Bounding the Number o f Primitive Propositions and the Depth o f Nesting on the Complexity o f Modal Logic // Artificial Intelligence. Vol. 75. 1995. P. 361-372.
8Ladner R.E. The computational complexity of provability in systems o f modal logic // SIAM Journal on Computing. Vol. 6. 1977. P. 467-480.
Nishimura /. On formulas of the one variable in intuitionistic propositional calculus II The Journal o f Symbolic Logic. Vol. 25. N. 1. 1960. P. 3 2 7 -331.
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' o f Problems // The Journal o f Symbolic Logic. Vol. 52. N .l. 1987. P. 1-43. (Русский перевод: Стокмейер Л. Классификация вычислительной сложности проблем // Кибернетический сборник, вып. 26. М.: Мир,, 1989. С. 20-83.)
Visser A. A Propositional Logic with Explicit Fixed Points // Studia Logica. Vol. 40. 1981. P. 155-175
Рыбаков М.Н., Чагров А.В. Модальные формулы без переменных и PSPACE-полнота // Современная логика: Проблемы теории, истории и применения в науке. Материалы VII Международной научной конференции. СПб: Издательство Санкт-Петербургского университета. 2002. С. 498-500.
Рыбаков М.Н., Чагров А. В. О сложности модальных логик, имеющих доказуемостную интерпретацию, с ограничениями на число переменных // Колмогоров и современная математика. Международная конференция. М.: Издательство МГУ, 2003. С. 707-708.
Семантика модальных и интенсиональных логик // Пер. с англ., сост., общ. ред. и вступит, статья В.А. Смирнова. М.: Прогресс, 1981.
Chagrov A., Zakharyaschev М. Modal Logic. Oxford University Press, 1997.
Garey M.R.., Johnson D.S. Computers and Intractability: A Guide to the Theory o f NP-completeness. San Francisco, 1979. (Русский перевод: Гэри M , Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982).
Halpern J. Y. The Effect o f Bounding the Number o f Primitive Propositions and the Depth o f Nesting on the Complexity o f Modal Logic // Artificial Intelligence. Vol. 75. 1995. P. 361-372.
8Ladner R.E. The computational complexity of provability in systems o f modal logic // SIAM Journal on Computing. Vol. 6. 1977. P. 467-480.
Nishimura /. On formulas of the one variable in intuitionistic propositional calculus II The Journal o f Symbolic Logic. Vol. 25. N. 1. 1960. P. 3 2 7 -331.
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' o f Problems // The Journal o f Symbolic Logic. Vol. 52. N .l. 1987. P. 1-43. (Русский перевод: Стокмейер Л. Классификация вычислительной сложности проблем // Кибернетический сборник, вып. 26. М.: Мир,, 1989. С. 20-83.)
Visser A. A Propositional Logic with Explicit Fixed Points // Studia Logica. Vol. 40. 1981. P. 155-175