Об алгоритмической выразительности модального языка с одной лишь одноместной предикатной буквой.
Article Sidebar
Опубликован:
03.10.2002
Main Article Content
Аннотация
Itis observed that fragments with only one monadic predicate letter of such logics as QK. QK4, QT, QS4, QGL, QGrz, and others are undecidable. It is proved that fragments with only one monadic predicate letter of $QGL^{em}$ and $QGrz^{em}$ (the sets of semantical consequences on Kripke frames of QGL and QGrz correspondently) are not recursively enumerable.
Скачивания
Данные скачивания пока не доступны.
Article Details
Как цитировать
Рыбаков М. Об алгоритмической выразительности модального языка с одной лишь одноместной предикатной буквой. // Логические исследования / Logical Investigations. 2002. Т. 9. C. 179-201.
Выпуск
Раздел
Статьи
Литература
Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994.
Маслов С.Ю., МинцГ.Е., Оревков В.П. Неразрешимость в конструктивном исчислении предикатов некоторых классов формул, содержащих только одноместные предикатные переменные // Доклады АН СССР. 1965. Т. 163, № 2. С. 295-297.
Рыбаков М.Н., Чагров А.В. Константные формулы в модальных логиках: проблема разрешения // См. настоящий сборник.
Рыбаков М.Н. Перечислимость модальных предикатных логик и условия обрыва возрастающих цепей // Логические исследования. Вып. 8. М.: Наука, 2001. С. 155-167.
Семантика модальных и интенсиональных логик. Сб. статей. Пер. с англ., сост., общ. ред. и вступит, статья В.А.Смирнова. М.: Прогресс, 1981.
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. No. 2, 1995. P. 361-372.
Kripke S.A. The Undecidability of modal quantification theory 11 Zeitschrift fiir Mathematische Logik und Grundlagen der Mathematik. Vol 8. 1962. P. 113-116. (Русский перевод: С.А. Крипке. Неразрешимость одноместного модального исчисления предикатов // Р. Фейс. Модальная логика. М.: Наука, 1974. С. 247-253.)
Montagna F. The Predicate Modal Logic of Provability 11Notre Dame Journal of Formal Logic. 1984. Vol. 25. N 2. P. 1059-1073.
Маслов С.Ю., МинцГ.Е., Оревков В.П. Неразрешимость в конструктивном исчислении предикатов некоторых классов формул, содержащих только одноместные предикатные переменные // Доклады АН СССР. 1965. Т. 163, № 2. С. 295-297.
Рыбаков М.Н., Чагров А.В. Константные формулы в модальных логиках: проблема разрешения // См. настоящий сборник.
Рыбаков М.Н. Перечислимость модальных предикатных логик и условия обрыва возрастающих цепей // Логические исследования. Вып. 8. М.: Наука, 2001. С. 155-167.
Семантика модальных и интенсиональных логик. Сб. статей. Пер. с англ., сост., общ. ред. и вступит, статья В.А.Смирнова. М.: Прогресс, 1981.
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. No. 2, 1995. P. 361-372.
Kripke S.A. The Undecidability of modal quantification theory 11 Zeitschrift fiir Mathematische Logik und Grundlagen der Mathematik. Vol 8. 1962. P. 113-116. (Русский перевод: С.А. Крипке. Неразрешимость одноместного модального исчисления предикатов // Р. Фейс. Модальная логика. М.: Наука, 1974. С. 247-253.)
Montagna F. The Predicate Modal Logic of Provability 11Notre Dame Journal of Formal Logic. 1984. Vol. 25. N 2. P. 1059-1073.