2025/05/20 by M. E. Vishnikin, Vishnikin, Maxim, Alexander Okhotin +1
Computer Science · #FOS: Mathematics #Logic (math.LO) #Natural Language Processing Techniques #Semantic Web and Ontologies #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2505.14559
openalex publication_date 2025/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Σ→ Ω+, 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.