TY - JOUR
T1 - The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages
AU - Kanazawa, Makoto
AU - Kobele, Gregory M.
AU - Michaelis, Jens
AU - Salvati, Sylvain
AU - Yoshinaka, Ryo
PY - 2014/7
Y1 - 2014/7
N2 - 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 {u0w1iu1...w2miu2m {pipe} i ∈ ℕ}, where w1⋯w2n≠ε. 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=u0w1u1⋯w2mu2m with w1⋯w2m≠ε and {u0w1iu1...w2miu2m {pipe} i ∈ ℕ} ⊂ L, has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.
AB - 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 {u0w1iu1...w2miu2m {pipe} i ∈ ℕ}, where w1⋯w2n≠ε. 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=u0w1u1⋯w2mu2m with w1⋯w2m≠ε and {u0w1iu1...w2miu2m {pipe} i ∈ ℕ} ⊂ L, has been open. We show that there is a 3-multiple context-free language that is not k-iterative for any k.
KW - Multiple context-free grammar
KW - Pumping lemma
UR - http://www.scopus.com/inward/record.url?scp=84901831016&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84901831016&partnerID=8YFLogxK
U2 - 10.1007/s00224-014-9534-z
DO - 10.1007/s00224-014-9534-z
M3 - Article
AN - SCOPUS:84901831016
SN - 1432-4350
VL - 55
SP - 250
EP - 278
JO - Theory of Computing Systems
JF - Theory of Computing Systems
IS - 1
ER -