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.
Original languageEnglish
Pages (from-to)635–664
Number of pages30
JournalJournal of Logic, Language and Information
Volume34
Issue number5
DOIs
StatePublished - 1 Nov 2025

    Research areas

  • Categorial grammars, Context-free grammars, Hardest languages, Unique category assignment

ID: 145262282