The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages

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 ₁⋯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 ₀ w ₁ u ₁⋯w _2m u _2m with w ₁⋯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.

1. Around the same time as Kasami et al. [9] first introduced multiple context-free grammars, essentially the same formalism was proposed by Vijay-Shanker et al. [15] under the name linear context-free rewriting systems (LCFRS). In this paper, we mostly follow the terminology of Seki et al. [14].

2. We let \(\mathbb {N}\) denote the set of natural numbers {0,1,2,…} and ε denote the empty string.

3. Formally, a context is a tree with a single special leaf node (“hole”), which is labeled by □. When U[] is a context and T is a tree, U[T] denotes the tree that results from removing the hole of U[] and inserting T in its place.

4. See footnote 10 of Radzinski [13]. Radzinski refers to the technical report [9] rather than the journal article [14] based on it, but the proof is the same in both papers.

5. A string v is a factor of a string z if z=uvw for some strings u,w.

6. As usual, the sets V,L,R are understood to be the components of the least solution to these equations.

7. By part (i), part (ii) can be equivalently stated with a ⁺ and b ⁺ in place of a ^∗ and b ^∗, but it will turn out to be slightly more convenient in this form.

8. We will appeal to Lemma 21 similarly in Cases 2–5 without explicitly going through this kind of reasoning.

Authors and Affiliations

1. National Institute of Informatics, 2-1-2 Hitotsubashi, Chiyoda-ku, Tokyo, 101-8430, Japan

   Makoto Kanazawa

2. Computation Institute and Department of Linguistics, University of Chicago, Chicago, IL, 60637, USA

   Gregory M. Kobele

3. Fakultät für Linguistik und Literaturwissenschaft, Universität Bielefeld, Postfach 10 01 31, 33501, Bielefeld, Germany

   Jens Michaelis

4. INRIA Bordeaux Sud-Ouest, LaBRI, 351, Cours de la Libération, 33405, Talence Cedex, France

   Sylvain Salvati

5. Graduate School of Informatics, Kyoto University, 36-1 Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501, Japan

   Ryo Yoshinaka

Corresponding author

Correspondence to Makoto Kanazawa.

Reprints and permissions