On the Expressive Power of Categorial Grammars: Representing Context-Free Formalisms

摘要

We show how to encode context-free string grammars, linear context-free tree grammars, and linear context-free rewriting systems as Categorial Grammars. These three encodings share the same constructs, the only difference being the interpretation of the composition of the production rules. It is interpreted as a first-order operation in the case of context-free string grammars, as a second-order operation in the case of linear context-free tree grammars, and as a third-order operation in the case of linear context-free rewriting systems. This suggest the possibility of defining an Categorial Hierarchy.