Paper: On The Succinctness Properties Of Unordered Context-Free Grammars

ACL ID P87-1016
Title On The Succinctness Properties Of Unordered Context-Free Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1987
Authors

We prove in this paper that unordered, or ID/LP grammars, are e.xponentially more succinct than context- free grammars, by exhibiting a sequence (L,~) of finite languages such that the size of any CFG for L,~ must grow exponentially in n, but which can be described by polynomial-size ID/LP grammars. The results have im- plications for the description of free word order languages.