{
  "id": "0901.1397",
  "version": "v1",
  "published": "2009-01-12T17:49:07.000Z",
  "updated": "2009-01-12T17:49:07.000Z",
  "title": "Avoiding Squares and Overlaps Over the Natural Numbers",
  "authors": [
    "Mathieu Guay-Paquet",
    "Jeffrey Shallit"
  ],
  "comment": "16 pages, 2 tables",
  "categories": [
    "math.CO",
    "cs.FL"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2009-01-12T17:49:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R15"
    ],
    "keywords": [
      "avoiding squares",
      "natural numbers",
      "familiar ruler function",
      "infinite overlap-free word",
      "infinite words"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}