|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
The complexity of multiplicative-additive Lambek calculus: 25 years laterстатья
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 4 мая 2020 г.
- Авторы: Kanovich Max, Kuznetsov Stepan, Scedrov Andre
- Сборник: WoLLIC 2019: Logic, Language, Information, and Computation
- Серия: Lecture Notes in Computer Science
- Том: 11541
- Год издания: 2019
- Место издания: Springer Berlin, Heidelberg
- Первая страница: 356
- Последняя страница: 372
- DOI: 10.1007/978-3-662-59533-6_22
- Аннотация: The Lambek calculus was introduced as a mathematical description of natural languages. The original Lambek calculus is NP-complete (Pentus), while its product-free fragment with only one implication is polynomially decidable (Savateev). We consider Lambek calculus with the additional connectives: conjunction and disjunction. It is known that this system is PSPACE-complete (Kanovich, Kanazawa). We prove, in contrast with the polynomial-time result for the product-free Lambek calculus with one implication, that the derivability problem is still PSPACE-complete even for a very small fragment (∖,∧), including one implication and conjunction only. PSPACE-completeness is also provided for the (∖,∨) fragment, which includes only one implication and disjunction. Categorial grammars based on the original Lambek calculus generate exactly the class of context-free languages (Gaifman, Pentus). The class of languages generated by Lambek grammars extended with conjunction is known to be closed under intersection (Kanazawa), and therefore includes all finite intersections of context-free languages and, moreover, images of such intersections under alphabetic homomorphisms. We show that the same closure under intersection holds for Lambek grammars extended with disjunction, even for our small (∖,∨) fragment.
- Добавил в систему: Кузнецов Степан Львович