PUB - Publikationen an der Universität Bielefeld

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₀w_1ⁱ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_2mu_2m with w₁···w_2m≠ε and {u₀w_1ⁱ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.