Categorial grammars with unique category assignment
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908372359446528 |
|---|---|
| author | Vishnikin, Maxim Okhotin, Alexander |
| author_facet | Vishnikin, Maxim Okhotin, Alexander |
| contents | A categorial grammar assigns one of several syntactic categories to each symbol of the alphabet, and the category of a string is then deduced from the categories assigned to its symbols using two simple reduction rules. This paper investigates a special class of categorial grammars, in which only one category is assigned to each symbol, thus eliminating ambiguity on the lexical level (in linguistic terms, a unique part of speech is assigned to each word). While unrestricted categorial grammars are equivalent to the context-free grammars, the proposed subclass initially appears weak, as it cannot define even some regular languages. It is proved in the paper that it is actually powerful enough to define a homomorphic encoding of every context-free language, in the sense that for every context-free language $L$ over an alphabet $Σ$ there is a language $L'$ over some alphabet $Ω$ defined by categorial grammar with unique category assignment and a homomorphism $h \colon Σ\to Ω^+$, such that a string $w$ is in $L$ if and only if $h(w)$ is in $L'$. In particular, in Greibach's hardest context-free language theorem, it is sufficient to use a hardest language defined by a categorial grammar with unique category assignment. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_14559 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Categorial grammars with unique category assignment Vishnikin, Maxim Okhotin, Alexander Logic A categorial grammar assigns one of several syntactic categories to each symbol of the alphabet, and the category of a string is then deduced from the categories assigned to its symbols using two simple reduction rules. This paper investigates a special class of categorial grammars, in which only one category is assigned to each symbol, thus eliminating ambiguity on the lexical level (in linguistic terms, a unique part of speech is assigned to each word). While unrestricted categorial grammars are equivalent to the context-free grammars, the proposed subclass initially appears weak, as it cannot define even some regular languages. It is proved in the paper that it is actually powerful enough to define a homomorphic encoding of every context-free language, in the sense that for every context-free language $L$ over an alphabet $Σ$ there is a language $L'$ over some alphabet $Ω$ defined by categorial grammar with unique category assignment and a homomorphism $h \colon Σ\to Ω^+$, such that a string $w$ is in $L$ if and only if $h(w)$ is in $L'$. In particular, in Greibach's hardest context-free language theorem, it is sufficient to use a hardest language defined by a categorial grammar with unique category assignment. |
| title | Categorial grammars with unique category assignment |
| topic | Logic |
| url | https://arxiv.org/abs/2505.14559 |