|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Algorithmic properties of first-order modal logics of the natural number line in restricted languagesстатья
- Авторы: Rybakov Mikhail, Shkatov Dmitry
- Сборник: Advances in Modal Logic
- Серия: Advances in Modal Logic
- Том: 13
- Год издания: 2020
- Место издания: College Publications London
- Первая страница: 523
- Последняя страница: 540
- Аннотация: We study algorithmic properties of first-order predicate monomodal logics of the frames (ℕ,<) and (ℕ,≤) in languages with restrictions on the number of individual variables as well as the number and arity of predicate letters. The languages we consider have no constants, function symbols, or the equality symbol. We show that satisfiability for the logic of (ℕ,<) is Σ11-hard in languages with two individual variables and two monadic predicate letters. We also show that satisfiability for the logic of (ℕ,≤) is Σ11-hard in languages with two individual variables, two monadic, and one 0-ary predicate letter. Thus, these logics are Π11-hard, and therefore not recursively enumerable, in languages with the aforementioned restrictions.
- Добавил в систему: Золин Евгений Евгеньевич