|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Complexity of the infinitary Lambek calculus with Kleene starстатья
Статья опубликована в высокорейтинговом журнале
Статья опубликована в журнале из списка Web of Science и/или Scopus- Автор: Kuznetsov Stepan
- Журнал: Review of Symbolic Logic
- Том: 14
- Номер: 4
- Год издания: 2020
- Первая страница: 946
- Последняя страница: 972
- DOI: 10.1017/s1755020320000209
- Аннотация: We consider the Lambek calculus, or noncommutative multiplicative intuitionistic linear logic, extended with iteration, or Kleene star, axiomatised by means of an omega-rule, and prove that the derivability problem in this calculus is \Pi^0_1-hard. This solves a problem left open by Buszkowski (2007), who obtained the same complexity bound for infinitary action logic, which additionally includes additive conjunction and disjunction. As a by-product, we prove that any context-free language without the empty word can be generated by a Lambek grammar with unique type assignment, without Lambek’s nonemptiness restriction imposed (cf. Safiullin, 2007).
- Добавил в систему: Кузнецов Степан Львович