×

A propos d’une conjecture de F. Dejean sur les répétitions dans les mots. (French) Zbl 0536.68072

In this paper we deal with unavoidable repetitions in words over a fixed alphabet. Let a t-repetition (for some rational t) be a word of the form \(u^ iv\) where v is a prefix of u and \(| u^ iv| =t.| u|\). We say that t-repetitions are unavoidable over X if arbitrarily long words over X contain a subword which is a t-repetition. Since the old work of A. Thue [Norske Vid. Selsk. Skr. I, Mat.-Nat. Kl. Christiana 7, 1-22 (1906)] it is known that if \(| X| =2\), 2- repetitions are unavoidable but t-repetitions are avoidable for all \(t>2\). We say that 2 is the repetition threshold for 2 letter alphabets. Similarly, F. Dejean has shown [J. Comb. Theory, Ser. A 13, 90-99 (1972; Zbl 0245.20052)] that 7/4 is the repetition threshold for 3 letter alphabets. In both cases, the proof relies on the construction of an infinite word by iterating morphism. We show that the threshold for \(| X| =4\) is 7/5, thereby solving a conjecture of Dejean. Moreover we use a more general way to construct an infinite word by first iterating a morphism and then applying a sequential machine to get a new infinite word. For \(| X| \geq 5\), the threshold is still unknown.

MSC:

68T99 Artificial intelligence
68Q45 Formal languages and automata
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.

Citations:

Zbl 0245.20052
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Arson, A., Démonstration de l’existence de suites asymétriques infinies, Mat. Sb., 44, 769-777 (1937) · Zbl 0018.11503
[2] Berstel, J., Sur les mots sans carré définis par un morphisme, Proc. 6th Int. Colloquium in Automata, Language and Programming, 71, 16-29 (1979), Lecture Notes in Computer Science · Zbl 0425.20046
[3] Berstel, J., Mots sans carrés et morphismes itérés, Discrete Math., 29, 235-244 (1979) · Zbl 0444.20050
[4] Brandenburg, F.-J., Uniformly growing \(k\) th power-free homomorphisms, Theoret. Comput. Sci., 23, 69-82 (1983) · Zbl 0508.68051
[5] Dejean, F., Sur un théorème de Thue, J. Combin. Theory (A), 13, 90-99 (1972) · Zbl 0245.20052
[6] Dekking, F. M., On repetitions of blocs in binary sequences, J. Combin. Theory (A), 20, 292-299 (1976) · Zbl 0325.05010
[7] Ehrenfeucht, A.; Lee, K. P.; Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interaction, Theoret. Comput. Sci., 1, 59-75 (1975) · Zbl 0316.68043
[8] Ehrenfeucht, A.; Rozenberg, G., On the subword complexity of square-free DOL languages, Proc. 5th GI Conf. Theoretical Computer Science, 104, 1-4 (1981), Lecture Notes in Computer Science · Zbl 0481.68073
[9] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[10] Morse, M.; Hedlund, G. A., Unending chess, symbolic dynamics, and a problem in semigroups, Duke Math. J., 11, 1-7 (1944) · Zbl 0063.04115
[11] Thue, A., Über unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I Mat.-Nat. Kl. Christiana, 7, 1-22 (1906) · JFM 39.0283.01
[12] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I Mat.-Nat. Kl. Christiana, 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.