Some Recent Results on Squarefree Words
Berstel, Jean
Publications du Département de mathématiques (Lyon), (1985), p. 21-36 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1985-01-01
@article{PDML_1985___2B_21_0,
     author = {Berstel, Jean},
     title = {Some Recent Results on Squarefree Words},
     journal = {Publications du D\'epartement de math\'ematiques (Lyon)},
     year = {1985},
     pages = {21-36},
     mrnumber = {848821},
     zbl = {0605.03015},
     language = {en},
     url = {http://dml.mathdoc.fr/item/PDML_1985___2B_21_0}
}

Berstel, Jean. Some Recent Results on Squarefree Words. Publications du Département de mathématiques (Lyon),  (1985), pp. 21-36. http://gdmltest.u-ga.fr/item/PDML_1985___2B_21_0/

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 0434.68056

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

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

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

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

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

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

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

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

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 614317 | Zbl 0472.10035

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

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

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

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

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

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

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 388861 | Zbl 0316.68043

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

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

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

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

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

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 178064 | Zbl 0123.02002

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 228875 | Zbl 0153.33101

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

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

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

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

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

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

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 756167 | Zbl 0547.68083

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

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

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

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

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

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

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

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

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 635134 | Zbl 0467.68063

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

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 618124 | Zbl 0487.68063

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

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 0495.68078

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

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

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

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

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

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

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

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