|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ЦЭМИ РАН |
||
Decidable Fragments of Calculi Used in CatLogстатья
- Авторы: Kanovich Max I., Kuznetsov Stepan G., Kuznetsov Stepan L., Scedrov Andre
- Сборник: Natural Language Processing in Artificial Intelligence — NLPinAI 2021
- Серия: Studies in Computational Intelligence (SCI)
- Том: 999
- Год издания: 2022
- Издательство: Springer International Publishing AG
- Местоположение издательства: Cham, Switzerland
- Первая страница: 1
- Последняя страница: 24
- DOI: 10.1007/978-3-030-90138-7_1
- Аннотация: CatLog is a categorial grammar parser/theorem-prover developed by Glyn Morrill and his co-authors. CatLog is based on an extension of Lambek calculus. A distinctive feature of this extension is the usage of brackets for controlled non-associativity and a subexponential modality whose contraction rule interacts with bracketing in a sophisticated way. We consider two variants of the calculus, appearing in different versions of CatLog. Both systems are, unfortunately, undecidable in general. We consider fragments where the usage of subexponential is restricted by so-called bracket non-negative/non-positive conditions, prove that these fragments are decidable, and pinpoint their place in the complexity hierarchy. We also consider a more complicated, but more practically interesting problem of inducing (guessing) brackets. For this problem, we prove one decidability and one undecidability result, and leave some open questions for further research.
- Добавил в систему: Кузнецов Степан Львович