Some Recent Results on Squarefree Words

Berstel, Jean

Publications du Département de mathématiques (Lyon), no. 2B (1985), pp. 21-36.

1 Autebert J. , J. Beauquier, L. Boasson, M. Nivat, Quelques problèmes ouverts en théorie des langages algébriques. RAIRO Informatique théorique 13 (1979), 363-379. | Numdam | Zbl

2 Adjan S., The Burnside problem and identities in groups", Ergeb. Math. Grenzgeb. vol. 95, Springer 1979. | MR | Zbl

3 Apostolico A., F. Preparata, Optimal off-line detection of repetitions in a string, Theor. Comp. Sci. 22 (1983), 297-315. | MR | Zbl

4 Bean D., A. Ehrenfeucht, G. Mcnulty, Advoidable patterns in strings of symbols, Pacific J. Math. 85 (1979), 261-294. | MR | Zbl

5 Brandeburg F., Uniformly growing K-th power-free homomorphisms, Theor. Comput. Sci. 23 (1983), 69-82. | MR | Zbl

6 Brinkhuis J. Non-repetitive sequences on three symbols, Quart. J. Math. Oxford (2) 34 (1983), 145-149. | MR | Zbl

7 Brzozowski J., K. Culik Ii , A. Gabrielian, Classification of noncounting events, J. Comp. Syst. Sci. 5 (1971), 41-53. | MR | Zbl

8 Carpi A., On the size of a square-free morphism on a three letter alphabet, Inf. Proc. Letters 16 (1983), 231-236. | MR | Zbl

9 Cerny A., On generalized words of Thue-Morse, Techn. Report, Université Paris VI, L.I.P.T. 83-84. | Zbl

10 Christol C., T. Kamae, M. Mendes-France, G. Rauzy, Suites algébriques automates et substitutions, Bull. Soc. Math. France 108 (1980), 401-419. | Numdam | MR | Zbl

11 Crochemore M., An optimal algorithm for computing the repetitions in a word, Inf. Proc. Letters, 12 (1981), 244-250. | MR | Zbl

12 Crochemore M. , Sharp characterizations of squarefree morphisms, Theor. Comp. Sci. 18 (1982), 221-226. | MR | Zbl

13 Crochemore M. Mots et morphismes sans carré, Annals of Discr. Math. 17 (1983), 235-245. | MR | Zbl

14 Crochemore M., Recherche linéaire d'un carré dans un mot, C. R. Acad. Sci. Paris, 296 (1983) , 781-784. | MR | Zbl

15 Dejean F., Sur un théorème de Thue, J. Combinatorial Theory 13 (1972), 90-99. | MR | Zbl

16 Ehrenfeucht A., D. Haussler, G. Rozenberg, Conditions enforcing regularity of context-free languages, Techn. Report, Boulder University, 1982. | MR | Zbl

17 Ehrenfeucht A., K. Lee, G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without iteraction, Theor. Comput. Sci. 1 (1975), 59-75. | MR | Zbl

18 Ehrenfeucht A., G. Rozenberg, On the subword complexity of square-free DOL languages, Theor. Comp. Sci. 16 (1981), 25-32. | MR | Zbl

19 Ehrenfeucht A., G. Rozenberg, Repetitions in homomorphisms and languages, 9th ICALP Symposium, Springer Lecture Notes in Computer Science 1982 192-196. | MR | Zbl

20 Ehrenfeucht A., G. Rozenberg, On the separating power of EOL systems RAIRO Informatique 17 (1983), 13-22. | Numdam | MR | Zbl

21 Gottschalk W., G. Hedlund, "Topological Dynamics", American Math. Soc. Colloq. Pub. Vol. 36, 1955. | MR | Zbl

22 Goldstine J., Bounded AFLs, J. Comput. Syst. Sci. 12 (1976), 399-419. | MR | Zbl

23 Hall M., Generators and relations in groups - the Burnside problem in : T.L. Saaty (ed.), "Lectures in Modern Mathematics", Vol. II, John Wiley & Sons, 1964 , 42-92. | MR | Zbl

24 Harju T., Morphisms that avoid overlapping, University of Turku May 1983.

25 Hedlund G., Remarks on the work of Axel Thue on sentences, Nord. Mat. Tidskr 16 (1967), 148-1. | MR | Zbl

26 Istrail S., On irreductible languages and non rational numbers, Bull. Mat. Soc. Sci. Mat. R. S. Roumanie 21 (1977), 301-308. | MR | Zbl

27 Karhumaki J., On cube-free $\omega$-words generated by binary morphisms, Discr. Appl. Math. 5 (1983), 279-297. | MR | Zbl

28 Leconte M., A fine characterization of power-free morphisms, Techn. Report L.I.T.P. 1984. | Zbl

29 Li S., Annihilators in non repetitive semi groups, Studies in Appl. Math. 55 (1976), 83-85. | Zbl

30 Lothaire M., "Combinatorics on Words", Addison-Wesley 1983. | MR | Zbl

31 Main M., Permutations are not context-free : an application of the "Interchange Lemma", Inf. Proc. Letters 15 (1982), 68-71. | MR | Zbl

32 Main M., R. Lorentz, An $0(nlogn)$ algorithm for recognizing repetition, Washington State University, Techn. Report CS-79-056.

33 Main M., R. Lorentz, An $0(nlogn)$ algorithm for finding all repetitions in a string, J. Algorithms, 1983, to appear. | MR | Zbl

34 Mccreight E. A space-economical suffix tree construction algorithm J. Assoc. Mach. Comp. 23 (1976) 262-272. | MR | Zbl

35 Minsky S., "Computations : finite and infinite machines", Prentice-Hall 1967. | MR | Zbl

36 Morse M., Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc. 22 (1921), 84-100. | JFM | MR

37 Morse M., G. Hedlund, Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J. 11 (1944), 1-7. | MR | Zbl

38 Ogden W., R. Ross, K. Winklmann, Ann "Interchange lemma" for context-free languages, Washington State University, Techn. Report CS-81-080. | Zbl

39 Pansiot J., The Morse sequence and iterated morphisms, Inf. Proc. Letters 12 (1981), 68-70. | MR | Zbl

40 Pansiot J., A propos d'une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math. | Zbl

41 Pleasants P., Nonrepetitive sequences, Proc. Cambridge Phil. Soc. 68 (1970) 267-274. | MR | Zbl

42 Restivo A., S. Salemi, On weakly square free words, Inf. Proc. Letters, to appear.

43 Reutenauer C., A new characterization of the regular languages, 8th ICALP, Springer Lecture Notes in Computer Science 115, 1981, 175-183. | MR | Zbl

44 Ross R., K. Winklmann, Repetitive strings are not context-free, RAIRO Informatique théorique 16 (1982), 191-199. | Numdam | MR | Zbl

45 Salomaa A., Morphisms on free monoids and language theory, in : R. Book (ed.) : "Formal language theory : perpectives and open problems", Academic Press 1098, 141-166.

46 Salomaa A., "Jewels of Formal Language Theory", Pitman 1981. | MR | Zbl

47 Seebold P., Morphismes itérés, mot de Morse et mot de Fibonacci, CR. Acad. Sci. Paris, 295 (1982), 439-441. | MR | Zbl

48 Seebold P., Sur les morphismes qui engendrent des mots infinis ayant des facteurs prescrits, 6. GI Tagung Theoretische Informatik Lecture Notes Comp. Sci. 145, 1983, 301-311. | Zbl

49 Seebold P., Sequences generated by infinitely iterated morphisms Techn. Report Université de Paris VII, L.I.T.P. 83-13. | Zbl

50 Shelton R., Aperiodic words on three symbols, I, II, J. Reine Angew, Math. 321 (1981), 195-209, 327 (1981), 1-11. | MR | Zbl

51 Shelton R., R. Soni, Aperiodic words on three symbols III, J. Reine Angew, Math. 330 (1982), 44-52. | MR | Zbl

52 Shyr J. , A stongly primitive word of arbitrary length ant its applications, Int. J. Comp. Math. A-6 (1970), 165-170. | MR | Zbl

53 Slisenko A., Determination in real time of all the periodicities in a word, Soviet Math. Dokl. 21 (1980), 392-395. | MR | Zbl

54 Thue A., Uber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania (1906), 1-22. | JFM

55 Thue A., Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania (1912), 1-67. | JFM

56 Weiner P., Linear pattern matching algorithms, Proc. 14 th Symp. switching automata theory, 1973. 1-11. | MR