{
  "id": "0904.3997",
  "version": "v4",
  "published": "2009-04-25T18:44:26.000Z",
  "updated": "2015-03-03T16:22:59.000Z",
  "title": "Generalized de Bruijn words for Primitive words and Powers",
  "authors": [
    "Yu Hin Au"
  ],
  "comment": "New results added, corrections made",
  "categories": [
    "math.CO"
  ],
  "abstract": "We show that for every $n \\geq 1$ and over any finite alphabet, there is a word whose circular factors of length $n$ have a one-to-one correspondence with the set of primitive words. In particular, we prove that such a word can be obtained by a greedy algorithm, or by concatenating all Lyndon words of length $n$ in increasing lexicographic order. We also look into connections between de Bruijn graphs of primitive words and Lyndon graphs. Finally, we also show that the shortest word that contains every $p$-power of length $pn$ over a $k$-letter alphabet has length between $pk^n$ and roughly $(p+ \\frac{1}{k}) k^n$, for all integers $p \\geq 1$. An algorithm that generates a word which achieves the upper bound is provided.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2013-08-30T21:13:51.000Z",
      "title": "Shortest sequences containing primitive words and powers",
      "abstract": "We show that for every $n$ and over any finite alphabet, there is a word whose circular factors of length $n$ have a one-to-one correspondence with the set of primitive words. In particular, we prove that such a word can be obtained by a greedy algorithm, or by concatenating all Lyndon words of length $n$ in increasing lexicographic order. We also look into connections between de Bruijn graphs of primitive words and Lyndon graphs. Finally, we also show that the shortest word that contains every $p$-power of length $pn$ over $\\set{0, \\ldots, k-1}$ has length roughly between $pk^n$ and $(p+ \\frac{1}{k}) k^n$, for all $p \\geq 1$ such that $pn$ is an integer. An algorithm that generates a word which achieves the upper bound is provided.",
      "comment": "new results added",
      "journal": null,
      "doi": null
    },
    {
      "version": "v4",
      "updated": "2015-03-03T16:22:59.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "shortest sequences containing primitive words",
      "one-to-one correspondence",
      "finite alphabet",
      "greedy algorithm",
      "lyndon words"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2009arXiv0904.3997H"
    }
  }
}