×
Main, Michael G.

An infinite square-free co-CFL. (English) Zbl 0556.68041

Inf. Process. Lett. 20, 105-107 (1985).

Cited in 10 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

context-free languages; repititions; pumping lemmas
Cite Review PDF
Full Text: DOI

References:

[1] Autebert, J. M.; Beauquier, J.; Boasson, L.; Nivat, M., Quelques problems ouverts en theorie des languages algebriques, RAIRO Informatique Théorique/Theoretical Informatics, 13, 4, 363-378 (1979) · Zbl 0434.68056
[2] Autebert, J. M.; Beauquier, J.; Boasson, L.; Latteux, M., Very small families of algebraic nonrational languages, (Book, R., Formal Language Theory: Perspectives and Open Problems (1980), Academic Press: Academic Press New York), 89-108
[3] Braunholtz, C. H., Solution to Problem 5030, Amer. Math. Monthly, 70, 675-676 (1963)
[4] Cobham, A., Uniform tag sequences, Math. Systems Theory, 6, 164-191 (1972) · Zbl 0253.02029
[5] Ehrenfeucht, A.; Rozenberg, G., On the subword complexity and square-freeness of formal languages, (Theoretical Computer Science 5th GI Conference. Theoretical Computer Science 5th GI Conference, Lecture Notes in Computer Science, 104 (1981), Springer: Springer Berlin), 1-4 · Zbl 0547.68078
[6] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[7] Hedlund, G. A., MR 37 (1959), #4454 · Zbl 0153.33101
[8] Main, M. G., Permutations are not context-free: An application of the interchange lemma, Inform. Process. Lett., 68-71 (1982) · Zbl 0486.68077
[9] Ogden, W.; Ross, R.; Winklmann, K., An ‘Interchange Lemma’ for context-free languages, WSU Tech. Rept. CS-81-080 (1981), Pullman, WA
[10] Pleasants, P. A.B., Nonrepetitive sequences, (Proc. Cambridge Phil. Soc., 68 (1970)), 267-274 · Zbl 0237.05010
[11] Ross, R.; Winklmann, K., Repetitive strings are not context-free, RAIRO Informatique Théorique/Theoretical Informatics, 16, 191-199 (1982) · Zbl 0489.68071
[12] Thue, A., Uber unendliche Zeichenreihen, Norske Videnskabers Selskabs Skrifter Mat.-Nat. Kl. (Kristiania), 7, 1-22 (1906) · JFM 39.0283.01
[13] Thue, A., Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Videnskabers Selskabs Skrifter Mat.-Nat. Kl. (Kristiania), 1, 1-67 (1912) · JFM 44.0462.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.