The weak generative capacity of parenthesis-free categorial grammars
Joyce Friedman, Dawei Dai, Weiguo Wang · 1986
We study the weak generative capacity of a class of parenthesis free categorial grammars derived from those of Ades and Steedman by varying the set of reduction rules. With forward cancellation as the only rule, the grammars are weakly equivalent to context free grammars. When a backward combination rule is added, it is no longer possible to obtain all the context-free language. With suitable restriction of the forward partial rule, the languages are still context-free and a push-down automaton can be used for recognition. Using the unrestricted rule of forward partial combination, a context sensitive language is obtained.