{
  "id": "1103.4051",
  "version": "v3",
  "published": "2011-03-21T15:27:24.000Z",
  "updated": "2012-07-09T06:37:20.000Z",
  "title": "Languages invariant under more symmetries: overlapping factors versus palindromic richness",
  "authors": [
    "Edita Pelantová",
    "Štěpán Starosta"
  ],
  "comment": "22 pages, 1 figure",
  "categories": [
    "math.CO"
  ],
  "abstract": "Factor complexity $\\mathcal{C}$ and palindromic complexity $\\mathcal{P}$ of infinite words with language closed under reversal are known to be related by the inequality $\\mathcal{P}(n) + \\mathcal{P}(n+1) \\leq 2 + \\mathcal{C}(n+1)-\\mathcal{C}(n)$ for any $n\\in \\mathbb{N}$\\,. Word for which the equality is attained for any $n$ is usually called rich in palindromes. In this article we study words whose languages are invariant under a finite group $G$ of symmetries. For such words we prove a stronger version of the above inequality. We introduce notion of $G$-palindromic richness and give several examples of $G$-rich words, including the Thue-Morse sequence as well.",
  "revisions": [
    {
      "version": "v3",
      "updated": "2012-07-09T06:37:20.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R15"
    ],
    "keywords": [
      "palindromic richness",
      "languages invariant",
      "overlapping factors",
      "symmetries",
      "palindromic complexity"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 22,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1103.4051P"
    }
  }
}