Conjunctive categorial grammars and Lambek grammars with additives
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916261403820032 |
|---|---|
| author | Kuznetsov, Stepan L. Okhotin, Alexander |
| author_facet | Kuznetsov, Stepan L. Okhotin, Alexander |
| contents | A new family of categorial grammars is proposed, defined by enriching basic categorial grammars with a conjunction operation. It is proved that the formalism obtained in this way has the same expressive power as conjunctive grammars, that is, context-free grammars enhanced with conjunction. It is also shown that categorial grammars with conjunction can be naturally embedded into the Lambek calculus with conjunction and disjunction operations. This further implies that a certain NP-complete set can be defined in the Lambek calculus with conjunction. We also show how to handle some subtle issues connected with the empty string. Finally, we prove that a language generated by a conjunctive grammar can be described by a Lambek grammar with disjunction (but without conjunction). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_16662 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Conjunctive categorial grammars and Lambek grammars with additives Kuznetsov, Stepan L. Okhotin, Alexander Logic in Computer Science Computation and Language Logic 03D05 F.4.2; F.4.1 A new family of categorial grammars is proposed, defined by enriching basic categorial grammars with a conjunction operation. It is proved that the formalism obtained in this way has the same expressive power as conjunctive grammars, that is, context-free grammars enhanced with conjunction. It is also shown that categorial grammars with conjunction can be naturally embedded into the Lambek calculus with conjunction and disjunction operations. This further implies that a certain NP-complete set can be defined in the Lambek calculus with conjunction. We also show how to handle some subtle issues connected with the empty string. Finally, we prove that a language generated by a conjunctive grammar can be described by a Lambek grammar with disjunction (but without conjunction). |
| title | Conjunctive categorial grammars and Lambek grammars with additives |
| topic | Logic in Computer Science Computation and Language Logic 03D05 F.4.2; F.4.1 |
| url | https://arxiv.org/abs/2405.16662 |