{
  "id": "1301.5104",
  "version": "v1",
  "published": "2013-01-22T08:27:59.000Z",
  "updated": "2013-01-22T08:27:59.000Z",
  "title": "On a generalization of Abelian equivalence and complexity of infinite words",
  "authors": [
    "Juhani Karhumaki",
    "Aleksi Saarela",
    "Luca Q. Zamboni"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In this paper we introduce and study a family of complexity functions of infinite words indexed by $k \\in \\ints ^+ \\cup {+\\infty}.$ Let $k \\in \\ints ^+ \\cup {+\\infty}$ and $A$ be a finite non-empty set. Two finite words $u$ and $v$ in $A^*$ are said to be $k$-Abelian equivalent if for all $x\\in A^*$ of length less than or equal to $k,$ the number of occurrences of $x$ in $u$ is equal to the number of occurrences of $x$ in $v.$ This defines a family of equivalence relations $\\thicksim_k$ on $A^*,$ bridging the gap between the usual notion of Abelian equivalence (when $k=1$) and equality (when $k=+\\infty).$ We show that the number of $k$-Abelian equivalence classes of words of length $n$ grows polynomially, although the degree is exponential in $k.$ Given an infinite word $\\omega \\in A^\\nats,$ we consider the associated complexity function $\\mathcal {P}^{(k)}_\\omega :\\nats \\rightarrow \\nats$ which counts the number of $k$-Abelian equivalence classes of factors of $\\omega$ of length $n.$ We show that the complexity function $\\mathcal {P}^{(k)}$ is intimately linked with periodicity. More precisely we define an auxiliary function $q^k: \\nats \\rightarrow \\nats$ and show that if $\\mathcal {P}^{(k)}_{\\omega}(n)<q^k(n)$ for some $k \\in \\ints ^+ \\cup {+\\infty}$ and $n\\geq 0,$ the $\\omega$ is ultimately periodic. Moreover if $\\omega$ is aperiodic, then $\\mathcal {P}^{(k)}_{\\omega}(n)=q^k(n)$ if and only if $\\omega$ is Sturmian. We also study $k$-Abelian complexity in connection with repetitions in words. Using Szemer\\'edi's theorem, we show that if $\\omega$ has bounded $k$-Abelian complexity, then for every $D\\subset \\nats$ with positive upper density and for every positive integer $N,$ there exists a $k$-Abelian $N$ power occurring in $\\omega$ at some position $j\\in D.$",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-01-22T08:27:59.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R15"
    ],
    "keywords": [
      "infinite word",
      "abelian equivalence classes",
      "generalization",
      "abelian complexity",
      "finite non-empty set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1301.5104K"
    }
  }
}