Abstract:

A categorial grammar is a classical formalism, in which each symbol of the alphabet is assigned 
one of several syntactic categories. The category of a string is then reduced from the categories assigned to its symbols, using two reduction rules. This paper investigates a special class of categorial grammars, in which the number of categories assigned to each symbol is bounded by arbitrary constant $k$ and categories have a special form. It is proved that an infinite hierarchy exists in 
the class of languages defined by such grammars.  Subsequently, the case of $k=2$ is studied.