On the Succinctness Properties of Unordered Context-Free Grammars

ON THE SUCCINCTNESS PROPERTIES OF UNORDERED CONTEXT-FREE GRAMMARS M. Drew Moshier and William C. Rounds Electrical Engineering and Computer Science Department University of Michigan Ann Arbor, Michigan 48109 1 Abstract 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. 2 Introduction Context free grammars in immediate dominance and linear precedence format were used in GPSG [3] as a skele- ton for metarule generation and feature checking. It is in- tuitively obvious that grammars in this form can describe languages which are closed under the operation of taking arbitrary permutations of strings in the language. (Such languages will be called symmetric.) Ordinary context- free grammars, on the other hand, "seem to require that all permutations of right-hand sides of productions be ex- plicitly listed, in order to describe certain symmetric lan- guages. For an explicit example, consider the n-letter al- phabet E,~ = {al ..... a,~}. Let P,~ be the set of all strings which are permutations of exactly these letters. It seems obvious that no context-free grammar could generate this language without explicitly listing it. Now try to prove that this is the case. This is in essence what we do in this paper. We also hope to get the audience for the paper interested in why the proof works! To give some idea of the difficulty of our problem, we begin by recounting Barton's results [1] in this confer- ence in 1985. (There is a general discussion in [2].) He showed that the universal recognition problem (URP) for ID/LP grammars is NP-complete. 1 This means that if P :~ NP, then no polynomial algorithm can solve this problem. The difficulty of the problem seems to arise from the fact that the translation from an ID/LP gram- mar to a weakly equivalent CFG blows up exponentially. It is easy to show, assuming P ~ NP, that any reason- able transformation from ID/LP grammars to equivalent CFGs cannot be done in polynomial time; Rounds has done this as a remark in [8]. In this paper, we remove the hypothesis P ~: NP. That is, we can show that no algorithm whatever can effect the translation polynomi- The universal recognition problem is to tell for an ID/LP gram- mar G and a string w, whether or not w E L(G). ally in all cases. (Unfortunately, this does not solve the P - NP question!) Barton's reduction took a known NP-complete prob- lem, the vertex-cover problem, and reduced it to the URP for ID/LP. The reduction makes crucial use of grammars whose production size can be arbitrarily large. Define the fan-out of a grammar to be the largest total number of symbol occurrences on the right hand side of any …

Content truncated to 500 words