|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
How many variables does one need to prove PSpace-hardness of modal logicsстатья
- Авторы: Chagrov Alexander, Rybakov Michael
- Сборник: Advances in Modal Logic
- Серия: Advances in Modal Logic
- Том: 4
- Год издания: 2003
- Место издания: King's College Publications London
- Первая страница: 71
- Последняя страница: 82
- Аннотация: The main result of the paper is that the decision problem for the variable-free fragments of both K and K4 is PSpace-complete. It is also proved that the decision problem for one-variable fragments of S4, GRz, and GL is PSpace-complete, too. The questions about complexity of variable-free, one-variable, and two-variable fragments of some closed logics are discussed.
- Добавил в систему: Золин Евгений Евгеньевич
Прикрепленные файлы
| № | Имя | Описание | Имя файла | Размер | Добавлен |
|---|---|---|---|---|---|
| 1. | Полный текст | generated from ps-file | 2003_Chagrov_Rybakov_AiML_4.ps.pdf | 218,3 КБ | 15 февраля 2016 [ezolin] |