{
  "id": "0708.4389",
  "version": "v1",
  "published": "2007-08-31T16:49:21.000Z",
  "updated": "2007-08-31T16:49:21.000Z",
  "title": "Occurrences of palindromes in characteristic Sturmian words",
  "authors": [
    "Amy Glen"
  ],
  "comment": "17 pages",
  "journal": "Theoretical Computer Science 352 (2006) 31-46",
  "doi": "10.1016/j.tcs.2005.09.075",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "This paper is concerned with palindromes occurring in characteristic Sturmian words $c_\\alpha$ of slope $\\alpha$, where $\\alpha \\in (0,1)$ is an irrational. As $c_\\alpha$ is a uniformly recurrent infinite word, any (palindromic) factor of $c_\\alpha$ occurs infinitely many times in $c_\\alpha$ with bounded gaps. Our aim is to completely describe where palindromes occur in $c_\\alpha$. In particular, given any palindromic factor $u$ of $c_\\alpha$, we shall establish a decomposition of $c_\\alpha$ with respect to the occurrences of $u$. Such a decomposition shows precisely where $u$ occurs in $c_\\alpha$, and this is directly related to the continued fraction expansion of $\\alpha$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2007-08-31T16:49:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R15",
      "11A55"
    ],
    "keywords": [
      "characteristic sturmian words",
      "occurrences",
      "palindromes occur",
      "uniformly recurrent infinite word",
      "continued fraction expansion"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2007arXiv0708.4389G"
    }
  }
}