DOI

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.
Язык оригиналаанглийский
Страницы (с-по)635–664
Число страниц30
ЖурналJournal of Logic, Language and Information
Том34
Номер выпуска5
DOI
СостояниеОпубликовано - 1 ноя 2025

ID: 145262282