|
ИСТИНА |
Войти в систему Регистрация |
ИСТИНА ИНХС РАН |
||
Powerful and NP-Complete: Hypergraph Lambek Grammarsстатья Исследовательская статья Электронная публикация Глава в книге
- Автор: Pshenitsyn Tikhon
- Сборник: Graph Transformation - 14th International Conference, ICGT 2021, Held as Part of STAF 2021, Virtual Event, June 24-25, 2021, Proceedings
- Серия: Lecture Notes in Computer Science
- Том: 12741
- Год издания: 2021
- Место издания: Springer
- Первая страница: 102
- Последняя страница: 121
- DOI: 10.1007/978-3-030-78946-6
- Аннотация: We consider two approaches to generating formal string languages: context-free grammars and Lambek grammars, which are based on the Lambek calculus. They are equivalent in the sense that they generate the same set of languages (disregarding the empty word). It is well known that context-free grammars can be generalized to hyperedge replacement grammars (HRGs) preserving their main principles and properties. In this paper, we study a generalization of the Lambek grammars to hypergraphs and investigate the recognizing power of the new formalism. We show how to define the hypergraph Lambek calculus (HL), and then introduce hypergraph Lambek grammars based on HL. It turns out that such grammars recognize all isolated-node bounded languages generated by HRGs. However, they are more powerful than HRGs: they recognize at least finite intersections of such languages. Thus the Pentus theorem along with the pumping lemma and the Parikh theorem have no place for hypergraph Lambek grammars. Besides, it can be shown that hypergraph Lambek grammars are NP-complete, so they constitute an attractive alternative to HRGs, which are also NP-complete.
- Добавил в систему: Пшеницын Тихон Григорьевич