Avoiding Squares and Overlaps Over the Natural Numbers
| dc.creator | Guay-Paquet, Mathieu | |
| dc.creator | Shallit, Jeffrey | |
| dc.date | 2009-01-12 | |
| dc.date.accessioned | 2026-07-07T13:02:12Z | |
| dc.date.available | 2026-07-07T13:02:12Z | |
| dc.description | We consider avoiding squares and overlaps over the natural numbers, using a greedy algorithm that chooses the least possible integer at each step; the word generated is lexicographically least among all such infinite words. In the case of avoiding squares, the word is 01020103..., the familiar ruler function, and is generated by iterating a uniform morphism. The case of overlaps is more challenging. We give an explicitly-defined morphism phi : N* -> N* that generates the lexicographically least infinite overlap-free word by iteration. Furthermore, we show that for all h,k in N with h <= k, the word phi^{k-h}(h) is the lexicographically least overlap-free word starting with the letter h and ending with the letter k, and give some of its symmetry properties. | |
| dc.description | 16 pages, 2 tables | |
| dc.identifier | https://arxiv.org/abs/0901.1397 | |
| dc.identifier | http://arxiv.org/abs/0901.1397 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226373 | |
| dc.subject | Combinatorics | |
| dc.subject | Formal Languages and Automata Theory | |
| dc.subject | 68R15 | |
| dc.title | Avoiding Squares and Overlaps Over the Natural Numbers | |
| dc.type | text |