|
|||||
|
|
The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages |
|
| Authors: | Makoto Kanazawa Gregory M. Kobele Jens Michaelis Sylvain Salvati Ryo Yoshinaka |
| Affiliation: | 1. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan 2. Computation Institute and Department of Linguistics, University of Chicago, Chicago, IL, 60637, USA 3. Fakult?t für Linguistik und Literaturwissenschaft, Universit?t Bielefeld, Postfach 10 01 31, 33501, Bielefeld, Germany 4. INRIA Bordeaux Sud-Ouest, LaBRI, 351, Cours de la Libération, 33405, Talence Cedex, France 5. Graduate School of Informatics, Kyoto University, 36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501, Japan |
| Abstract: | Seki et al. (Theor. Comput. Sci. 88(2):191–229, 1991) showed that every m-multiple context-free language L is weakly 2m-iterative in the sense that either L is finite or L contains a subset of the form ({ u_{0} w_{1}^{i} u_{1} cdots w_{2m}^{i} u_{2m} mid i in mathbb {N}}) , where w 1?w 2n ≠ε. Whether every m-multiple context-free language L is 2m-iterative, that is to say, whether all but finitely many elements z of L can be written as z=u 0 w 1 u 1?w 2m u 2m with w 1?w 2m ≠ε and ({ u_{0} w_{1}^{i} u_{1} cdots w_{2m}^{i} u_{2m} mid i in mathbb {N}} subseteq L) , has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k. |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ | |
