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.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Kanazawa, Makoto; Kobele, Gregory M.; Michaelis, JensUniBi ; Salvati, Sylvain; Yoshinaka, Ryo
Abstract / Bemerkung
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.
Stichworte
Pumping lemma; Multiple context-free grammar
Erscheinungsjahr
2014
Zeitschriftentitel
Theory of Computing Systems
Band
55
Ausgabe
1
Seite(n)
250-278
ISSN
1432-4350
eISSN
1433-0490
Page URI
https://pub.uni-bielefeld.de/record/2684251

Zitieren

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. doi:10.1007/s00224-014-9534-z
Kanazawa, Makoto, Kobele, Gregory M., Michaelis, Jens, Salvati, Sylvain, and Yoshinaka, Ryo. 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.
Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®
Suchen in

Google Scholar