Makoto Kanazawa, Gregory M. Kobele, Jens Michaelis, Sylvain Salvati & Ryo Yoshinaka. The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages. Final version appeared in Theory of Computing Systems, 55(1):250-278, 2014.

Abstract

Seki et al. (Theoretical Computer Science 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_₀w_₁ⁱu_₁w_{_2m}ⁱu_{_2m}|i≥0}, where w_₁···w_{_2m}≠ε. 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_₀w_₁ⁱu_₁···w_{_2m}ⁱu_{_2m}|i≥0}⊆L, has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.

previous page personal homepage