TY - JOUR

T1 - On the expressive power of categorial grammars with unique category assignment

AU - Вишникин, Максим Евгеньевич

AU - Охотин, Александр Сергеевич

PY - 2025/11/1

Y1 - 2025/11/1

N2 - A categorial grammar assigns one of several synthetic 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. A subclass of categorial grammars, in which only one category is assigned to each symbol, thus eliminating ambiguity on the lexical level, has been studied under multiple names, such as rigid, 1-valued or deterministic categorial grammars. 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. This paper investigates the expressive power of this subclass; it is proved 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:Σ→Ω+, 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.

AB - A categorial grammar assigns one of several synthetic 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. A subclass of categorial grammars, in which only one category is assigned to each symbol, thus eliminating ambiguity on the lexical level, has been studied under multiple names, such as rigid, 1-valued or deterministic categorial grammars. 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. This paper investigates the expressive power of this subclass; it is proved 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:Σ→Ω+, 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.

KW - Categorial grammars

KW - Context-free grammars

KW - Hardest languages

KW - Unique category assignment

UR - https://www.mendeley.com/catalogue/7aa0e8d5-55a2-36e7-8487-2353e097c6f9/

U2 - 10.1007/s10849-025-09445-9

DO - 10.1007/s10849-025-09445-9

M3 - Article

VL - 34

SP - 635

EP - 664

JO - Journal of Logic, Language and Information

JF - Journal of Logic, Language and Information

SN - 0925-8531

IS - 5

ER -