Some Recent Results on Squarefree Words

 Access to full text

 Full (PDF)

1. 1 Autebert J. , J. Beauquier, L. Boasson, M. Nivat, Quelques problèmes ouverts en théorie des langages algébriques. RAIRO Informatique théorique13 (1979), 363-379. Zbl0434.68056
2. 2 Adjan S., The Burnside problem and identities in groups", Ergeb. Math. Grenzgeb. vol. 95, Springer1979. Zbl0417.20001MR537580
3. 3 Apostolico A., F. Preparata, Optimal off-line detection of repetitions in a string, Theor. Comp. Sci.22 (1983), 297-315. Zbl0497.68052MR693062
4. 4 Bean D., A. Ehrenfeucht, G. McNulty, Advoidable patterns in strings of symbols, Pacific J. Math.85 (1979), 261-294. Zbl0428.05001MR574919
5. 5 Brandeburg F., Uniformly growing K-th power-free homomorphisms, Theor. Comput. Sci.23 (1983), 69-82. Zbl0508.68051MR693069
6. 6 Brinkhuis J.Non-repetitive sequences on three symbols, Quart. J. Math. Oxford (2) 34 (1983), 145-149. Zbl0528.05004MR698202
7. 7 Brzozowski J., K. Culik II , A. Gabrielian, Classification of noncounting events, J. Comp. Syst. Sci.5 (1971), 41-53. Zbl0241.94050MR286578
8. 8 Carpi A., On the size of a square-free morphism on a three letter alphabet, Inf. Proc. Letters16 (1983), 231-236. Zbl0508.68052MR709659
9. 9 Cerny A., On generalized words of Thue-Morse, Techn. Report, Université Paris VI, L.I.P.T.83-84. Zbl0638.68090
10. 10 Christol C., T. Kamae, M. Mendes-France, G. Rauzy, Suites algébriques automates et substitutions, Bull. Soc. Math. France108 (1980), 401-419. Zbl0472.10035MR614317
11. 11 Crochemore M., An optimal algorithm for computing the repetitions in a word, Inf. Proc. Letters, 12 (1981), 244-250. Zbl0467.68075MR632873
12. 12 Crochemore M. , Sharp characterizations of squarefree morphisms, Theor. Comp. Sci.18 (1982), 221-226. Zbl0482.68085MR652471
13. 13 Crochemore M.Mots et morphismes sans carré, Annals of Discr. Math.17 (1983), 235-245. Zbl0527.20045MR841299
14. 14 Crochemore M., Recherche linéaire d'un carré dans un mot, C. R. Acad. Sci.Paris, 296 (1983) , 781-784. Zbl0522.68074MR707557
15. 15 Dejean F., Sur un théorème de Thue, J. Combinatorial Theory13 (1972), 90-99. Zbl0245.20052MR300959
16. 16 Ehrenfeucht A., D. Haussler, G. Rozenberg, Conditions enforcing regularity of context-free languages, Techn. Report, Boulder University, 1982. Zbl0495.68068MR675456
17. 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. Zbl0316.68043MR388861
18. 18 Ehrenfeucht A., G. Rozenberg, On the subword complexity of square-free DOL languages, Theor. Comp. Sci.16 (1981), 25-32. Zbl0481.68073MR632668
19. 19 Ehrenfeucht A., G. Rozenberg, Repetitions in homomorphisms and languages, 9th ICALP Symposium, SpringerLecture Notes in Computer Science1982192-196. Zbl0502.68020MR675457
20. 20 Ehrenfeucht A., G. Rozenberg, On the separating power of EOL systemsRAIRO Informatique17 (1983), 13-22. Zbl0512.68059MR701985
21. 21 Gottschalk W., G. Hedlund, "Topological Dynamics", American Math. Soc.Colloq. Pub. Vol. 36, 1955. Zbl0067.15204MR74810
22. 22 Goldstine J., Bounded AFLs, J. Comput. Syst. Sci.12 (1976), 399-419. Zbl0331.68043MR405937
23. 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. Zbl0123.02002MR178064
24. 24 Harju T., Morphisms that avoid overlapping, University of Turku May 1983. 
25. 25 Hedlund G., Remarks on the work of Axel Thue on sentences, Nord. Mat. Tidskr16 (1967), 148-1. Zbl0153.33101MR228875
26. 26 Istrail S., On irreductible languages and non rational numbers, Bull. Mat. Soc. Sci. Mat. R. S. Roumanie21 (1977), 301-308. Zbl0374.68053MR521207
27. 27 Karhumaki J., On cube-free $\omega$-words generated by binary morphisms, Discr. Appl. Math.5 (1983), 279-297. Zbl0505.03022MR690339
28. 28 Leconte M., A fine characterization of power-free morphisms, Techn. Report L.I.T.P.1984. Zbl0572.68066
29. 29 Li S., Annihilators in non repetitive semi groups, Studies in Appl. Math.55 (1976), 83-85. Zbl0334.05004
30. 30 Lothaire M., "Combinatorics on Words", Addison-Wesley1983. Zbl0514.20045MR675953
31. 31 Main M., Permutations are not context-free : an application of the "Interchange Lemma", Inf. Proc. Letters15 (1982), 68-71. Zbl0486.68077MR675871
32. 32 Main M., R. Lorentz, An $0(nlogn)$ algorithm for recognizing repetition, Washington State University, Techn. Report CS-79-056. 
33. 33 Main M., R. Lorentz, An $0(nlogn)$ algorithm for finding all repetitions in a string, J. Algorithms, 1983, to appear. Zbl0547.68083MR756167
34. 34 McCreight E.A space-economical suffix tree construction algorithmJ. Assoc. Mach. Comp.23 (1976) 262-272. Zbl0329.68042MR413594
35. 35 Minsky S., "Computations : finite and infinite machines", Prentice-Hall1967. Zbl0195.02402MR356580
36. 36 Morse M., Recurrent geodesics on a surface of negative curvature, Trans. Amer. Math. Soc.22 (1921), 84-100. Zbl48.0786.06MR1501161JFM48.0786.06
37. 37 Morse M., G. Hedlund, Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J.11 (1944), 1-7. Zbl0063.04115MR9788
38. 38 Ogden W., R. Ross, K. Winklmann, Ann "Interchange lemma" for context-free languages, Washington State University, Techn. Report CS-81-080. Zbl0601.68051
39. 39 Pansiot J., The Morse sequence and iterated morphisms, Inf. Proc. Letters12 (1981), 68-70. Zbl0464.68075MR613238
40. 40 Pansiot J., A propos d'une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math. Zbl0536.68072
41. 41 Pleasants P., Nonrepetitive sequences, Proc. Cambridge Phil. Soc.68 (1970) 267-274. Zbl0237.05010MR265173
42. 42 Restivo A., S. Salemi, On weakly square free words, Inf. Proc. Letters, to appear. 
43. 43 Reutenauer C., A new characterization of the regular languages, 8th ICALP, SpringerLecture Notes in Computer Science115, 1981, 175-183. Zbl0467.68063MR635134
44. 44 Ross R., K. Winklmann, Repetitive strings are not context-free, RAIRO Informatique théorique16 (1982), 191-199. Zbl0489.68071MR686912
45. 45 Salomaa A., Morphisms on free monoids and language theory, in : R. Book (ed.) : "Formal language theory : perpectives and open problems", Academic Press1098, 141-166. 
46. 46 Salomaa A., "Jewels of Formal Language Theory", Pitman1981. Zbl0487.68063MR618124
47. 47 Seebold P., Morphismes itérés, mot de Morse et mot de Fibonacci, CR. Acad. Sci.Paris, 295 (1982), 439-441. Zbl0506.20027MR683398
48. 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. Zbl0495.68078
49. 49 Seebold P., Sequences generated by infinitely iterated morphismsTechn. Report Université de Paris VII, L.I.T.P. 83-13. Zbl0583.20047
50. 50 Shelton R., Aperiodic words on three symbols, I, II, J. Reine Angew, Math.321 (1981), 195-209, 327 (1981), 1-11. Zbl0441.05007MR597989
51. 51 Shelton R., R. Soni, Aperiodic words on three symbols III, J. Reine Angew, Math.330 (1982), 44-52. Zbl0467.05010MR641810
52. 52 Shyr J. , A stongly primitive word of arbitrary length ant its applications, Int. J. Comp. Math. A-6 (1970), 165-170. Zbl0405.68066MR464747
53. 53 Slisenko A., Determination in real time of all the periodicities in a word, Soviet Math. Dokl.21 (1980), 392-395. Zbl0442.68033MR563176
54. 54 Thue A., Uber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania (1906), 1-22. JFM39.0283.01
55. 55 Thue A., Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania (1912), 1-67. JFM44.0462.01
56. 56 Weiner P., Linear pattern matching algorithms, Proc. 14 th Symp. switching automata theory, 1973. 1-11. MR441032