20:
of a finite or infinite sequence of symbols over a finite alphabet describes the largest number of times a contiguous subsequence can be repeated. For example, the critical exponent of "Mississippi" is 7/3, as it contains the string "ississi", which is of length 7 and period 3.
280:
446:=2, any binary word of length four has a factor of exponent 2, and since the critical exponent of the Thue–Morse sequence is 2, the repetition threshold for binary alphabets is RT(2) = 2. It is known that RT(3) = 7/4, RT(4) = 7/5 and that for
347:
198:
719:. Encyclopedia of Mathematics and Its Applications. Vol. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press.
190:
164:
288:
654:
Krieger, Dalia (2006). "On critical exponents in fixed points of non-erasing morphisms". In Ibarra, Oscar H.; Dang, Zhe (eds.).
656:
Developments in
Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26–29, 2006
724:
636:
603:
275:{\displaystyle E(\mathbf {w} )=\sup\{r\in \mathbb {Q} ^{\geq 1}:\mathbf {w} \,{\text{ contains an }}\,r{\text{-power}}\}}
759:
667:
791:
628:
595:
786:
173:
147:
462:-1). It is conjectured that the latter is the true value, and this has been established for 5 ≤
373:
769:
734:
677:
646:
613:
8:
743:
755:
720:
663:
632:
599:
479:
765:
730:
698:
673:
642:
609:
406:
751:
659:
587:
621:
Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009).
359:
703:
686:
780:
402:
712:
622:
376:
is 2. The word contains arbitrarily long squares, but in any factor
342:{\displaystyle \mathbb {Q} ^{\geq 1}=\{q\in \mathbb {Q} :q\geq 1\}}
121:
624:
Combinatorics on words. Christoffel words and repetitions in words
129:
430:
letters is the minimum critical exponent of infinite words over
746:; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.).
620:
398:
The critical exponent can take any real value greater than 1.
109:
if it contains no factors which are β-powers for any β ≥ α.
687:"Every real number greater than one is a critical exponent"
48:
with exponent α, for positive real α, if there is a factor
592:
Automatic
Sequences: Theory, Applications, Generalizations
564:
750:. Lecture Notes in Mathematics. Vol. 1794. Berlin:
748:
Substitutions in dynamics, arithmetics and combinatorics
627:. CRM Monograph Series. Vol. 27. Providence, RI:
658:. Lecture Notes in Computer Science. Vol. 4036.
291:
201:
176:
150:
341:
274:
184:
158:
778:
405:over a finite alphabet is either infinite or an
219:
585:
558:
684:
570:
741:
336:
310:
269:
222:
409:of degree at most the size of the alphabet.
85:is the integer part of α, and the length |
702:
509:
507:
320:
294:
260:
254:
233:
16:In mathematics and computer science, the
711:
166:is a word (possibly infinite), then the
653:
543:
531:
498:
413:
779:
554:
552:
527:
525:
523:
521:
519:
504:
28:is an infinite word over the alphabet
549:
516:
492:
13:
128:has α-powers, or equivalently the
14:
803:
685:Krieger, D.; Shallit, J. (2007).
717:Algebraic combinatorics on words
250:
209:
178:
152:
537:
213:
205:
1:
629:American Mathematical Society
579:
559:Allouche & Shallit (2003)
392:
372:The critical exponent of the
358:The critical exponent of the
139:
571:Krieger & Shallit (2007)
185:{\displaystyle \mathbf {w} }
159:{\displaystyle \mathbf {w} }
7:
473:
401:The critical exponent of a
352:
10:
808:
596:Cambridge University Press
513:Berstel et al (2009) p.126
742:Pytheas Fogg, N. (2002).
704:10.1016/j.tcs.2007.04.037
486:
434:: clearly this value RT(
257: contains an
792:Combinatorics on words
343:
276:
186:
160:
36:is a finite word over
586:Allouche, Jean-Paul;
344:
277:
187:
161:
662:. pp. 280–291.
482:of a physical system
420:repetition threshold
414:Repetition threshold
289:
199:
174:
148:
44:is said to occur in
384:is not a prefix of
374:Thue–Morse sequence
132:of the α for which
124:of the α for which
691:Theor. Comput. Sci
438:) depends only on
362:is (5 +
339:
272:
182:
156:
726:978-0-521-18071-9
638:978-0-8218-4480-9
605:978-0-521-82332-6
480:Critical exponent
267:
258:
192:is defined to be
168:critical exponent
136:is α-power-free.
114:critical exponent
18:critical exponent
799:
787:Formal languages
773:
738:
708:
706:
697:(1–3): 177–182.
681:
650:
617:
588:Shallit, Jeffrey
574:
568:
562:
556:
547:
541:
535:
529:
514:
511:
502:
496:
407:algebraic number
368:
367:
348:
346:
345:
340:
323:
306:
305:
297:
281:
279:
278:
273:
268:
265:
259:
256:
253:
245:
244:
236:
212:
191:
189:
188:
183:
181:
165:
163:
162:
157:
155:
807:
806:
802:
801:
800:
798:
797:
796:
777:
776:
762:
752:Springer-Verlag
744:Berthé, Valérie
727:
670:
660:Springer-Verlag
639:
606:
582:
577:
569:
565:
557:
550:
542:
538:
530:
517:
512:
505:
497:
493:
489:
476:
422:of an alphabet
416:
395:
365:
363:
355:
319:
298:
293:
292:
290:
287:
286:
264:
255:
249:
237:
232:
231:
208:
200:
197:
196:
177:
175:
172:
171:
151:
149:
146:
145:
142:
93:|: we say that
77:is a prefix of
76:
69:
12:
11:
5:
805:
795:
794:
789:
775:
774:
760:
739:
725:
709:
682:
668:
651:
637:
618:
604:
581:
578:
576:
575:
563:
548:
544:Krieger (2006)
536:
532:Krieger (2006)
515:
503:
499:Krieger (2006)
490:
488:
485:
484:
483:
475:
472:
450:≥5 we have RT(
415:
412:
411:
410:
399:
394:
391:
390:
389:
370:
360:Fibonacci word
354:
351:
338:
335:
332:
329:
326:
322:
318:
315:
312:
309:
304:
301:
296:
283:
282:
271:
263:
252:
248:
243:
240:
235:
230:
227:
224:
221:
218:
215:
211:
207:
204:
180:
154:
141:
138:
74:
67:
9:
6:
4:
3:
2:
804:
793:
790:
788:
785:
784:
782:
771:
767:
763:
761:3-540-44141-7
757:
753:
749:
745:
740:
736:
732:
728:
722:
718:
714:
710:
705:
700:
696:
692:
688:
683:
679:
675:
671:
669:3-540-35428-X
665:
661:
657:
652:
648:
644:
640:
634:
630:
626:
625:
619:
615:
611:
607:
601:
597:
593:
589:
584:
583:
572:
567:
560:
555:
553:
545:
540:
533:
528:
526:
524:
522:
520:
510:
508:
500:
495:
491:
481:
478:
477:
471:
469:
466:≤ 14 and for
465:
461:
457:
453:
449:
445:
441:
437:
433:
429:
425:
421:
408:
404:
400:
397:
396:
387:
383:
379:
375:
371:
361:
357:
356:
350:
333:
330:
327:
324:
316:
313:
307:
302:
299:
261:
246:
241:
238:
228:
225:
216:
202:
195:
194:
193:
169:
137:
135:
131:
127:
123:
119:
115:
110:
108:
104:
100:
96:
92:
88:
84:
80:
73:
66:
63:
59:
55:
51:
47:
43:
39:
35:
31:
27:
22:
19:
747:
716:
713:Lothaire, M.
694:
690:
655:
623:
591:
566:
539:
494:
467:
463:
459:
455:
451:
447:
443:
439:
435:
431:
427:
423:
419:
417:
403:morphic word
385:
381:
377:
369:)/2 ≈ 3.618.
284:
167:
143:
133:
125:
117:
113:
111:
107:α-power-free
106:
102:
101:. The word
98:
94:
90:
86:
82:
78:
71:
64:
61:
57:
53:
49:
45:
41:
37:
33:
29:
25:
23:
17:
15:
380:the letter
781:Categories
770:1014.11015
735:1221.68183
678:1227.68074
647:1161.68043
614:1086.11015
580:References
393:Properties
140:Definition
331:≥
317:∈
300:≥
239:≥
229:∈
715:(2011).
590:(2003).
474:See also
353:Examples
122:supremum
442:. For
364:√
130:infimum
120:is the
99:α-power
97:is an
89:| = α |
40:, then
768:
758:
733:
723:
676:
666:
645:
635:
612:
602:
470:≥ 33.
285:where
266:-power
70:where
561:p. 37
546:p.282
534:p.280
501:p.281
487:Notes
56:with
756:ISBN
721:ISBN
664:ISBN
633:ISBN
600:ISBN
454:) ≥
418:The
116:for
112:The
105:is
32:and
766:Zbl
731:Zbl
699:doi
695:381
674:Zbl
643:Zbl
610:Zbl
426:of
378:xxb
220:sup
170:of
144:If
52:of
24:If
783::
764:.
754:.
729:.
693:.
689:.
672:.
641:.
631:.
608:.
598:.
594:.
551:^
518:^
506:^
458:/(
349:.
81:,
60:=
772:.
737:.
707:.
701::
680:.
649:.
616:.
573:.
468:n
464:n
460:n
456:n
452:n
448:n
444:n
440:n
436:n
432:A
428:n
424:A
388:.
386:x
382:b
366:5
337:}
334:1
328:q
325::
321:Q
314:q
311:{
308:=
303:1
295:Q
270:}
262:r
251:w
247::
242:1
234:Q
226:r
223:{
217:=
214:)
210:w
206:(
203:E
179:w
153:w
134:w
126:w
118:w
103:w
95:y
91:x
87:y
83:a
79:x
75:0
72:x
68:0
65:x
62:x
58:y
54:w
50:y
46:w
42:x
38:A
34:x
30:A
26:w
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.