Avoiding Squares and Overlaps Over the Natural Numbers

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

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.
16 pages, 2 tables

Keywords

Combinatorics, Formal Languages and Automata Theory, 68R15

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/226373

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0901.1397
 http://arxiv.org/abs/0901.1397

Collections

arXiv