Paper: The Weak Generative Capacity Of Parenthesis-Free Categorial Grammars

ACL ID C86-1047
Title The Weak Generative Capacity Of Parenthesis-Free Categorial Grammars
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1986
Authors

We study the weak generative capacity of a class of parenthesis-free categorial grammars derived /torn those of Aries 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 back- ward combination rule is added, it is no longer possible to oh- lain all the context-free languages. With suitable restriction of the forward partial rule, the languages are still context-free and a push-down automaton can be used for recognition. Us- ing the unrestricted rule of forward partial combination, a context-sensitive language is obtained.