Some Recent Results on Squarefree Words

Berstel, Jean

Publications du Département de mathématiques (Lyon), Compte rendu des journées infinitistes, 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. | Zbl | Numdam

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

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

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

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

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

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

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

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. | Zbl | MR | Numdam

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

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

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

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

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

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

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. | Zbl | MR

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

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

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

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

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

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. | Zbl | MR

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. | Zbl | MR

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

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

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. | Zbl | MR

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

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. | Zbl | MR

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

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

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

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

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. | Zbl | MR

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. | Zbl | MR

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. | Zbl | MR

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

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. | Zbl | MR

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

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. | Zbl | MR

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

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

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

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