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

Kanazawa M, Kobele GM, Michaelis J, Salvati S, Yoshinaka R (2014)
Theory of Computing Systems 55(1): 250-278.

Journal Article | Published | English

No fulltext has been uploaded

Author
; ; ; ;
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 {u0w1iu1w2miu2m|i≥0}, where w1···w2m≠ε. 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=u0w1u1w2mu2m with w1···w2m≠ε and {u0w1iu1···w2miu2m|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.
Publishing Year
ISSN
eISSN
PUB-ID

Cite this

Kanazawa M, Kobele GM, Michaelis J, Salvati S, Yoshinaka R. The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages. Theory of Computing Systems. 2014;55(1):250-278.
Kanazawa, M., Kobele, G. M., Michaelis, J., Salvati, S., & Yoshinaka, R. (2014). The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages. Theory of Computing Systems, 55(1), 250-278.
Kanazawa, M., Kobele, G. M., Michaelis, J., Salvati, S., and Yoshinaka, R. (2014). The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages. Theory of Computing Systems 55, 250-278.
Kanazawa, M., et al., 2014. The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages. Theory of Computing Systems, 55(1), p 250-278.
M. Kanazawa, et al., “The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages”, Theory of Computing Systems, vol. 55, 2014, pp. 250-278.
Kanazawa, M., Kobele, G.M., Michaelis, J., Salvati, S., Yoshinaka, R.: The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages. Theory of Computing Systems. 55, 250-278 (2014).
Kanazawa, Makoto, Kobele, Gregory M., Michaelis, Jens, Salvati, Sylvain, and Yoshinaka, Ryo. “The Failure of the Strong Pumping Lemma for Multiple Context-Free Languages”. Theory of Computing Systems 55.1 (2014): 250-278.
This data publication is cited in the following publications:
This publication cites the following data publications:

Export

0 Marked Publications

Open Data PUB

Web of Science

View record in Web of Science®

Search this title in

Google Scholar