tailieunhanh - Báo cáo khoa học: "ON THE SUCCINCTNESS PROPERTIES OF UNORDERED CONTEXT-FREE GRAMMARS"

We prove in this paper that unordered, or I D / L P grammars, are more succinct than contextfree 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 I D / L P grammars. The results have implications for the description of free word order languages. | 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 exponentially more succinct than context-free grammars by exhibiting a sequence Ln of finite languages such that the size of any CFG for Ln must grow exponentially in n but which can be described by polynomial-size ID LP grammars. The results have implications 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 skeleton for metarule generation and feature checking. It is intuitively 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 perrputations of right-hand sides of productions be explicitly listed in order to describe certain symmetric languages. For an explicit example consider the n-letter alphabet Sn ai . an . Let pn 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 conference in 1985. There is a general discussion in 2 . He showed that the universal recognition problem URP for ID LP grammars is 2VP-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