{
  "id": "2201.04603",
  "version": "v2",
  "published": "2022-01-12T18:00:28.000Z",
  "updated": "2022-12-06T15:37:46.000Z",
  "title": "Characterizations of families of morphisms and words via binomial complexities",
  "authors": [
    "Michel Rigo",
    "Manon Stipulanti",
    "Markus A. Whiteland"
  ],
  "comment": "35 pages, 2 figures. Short version under a different title: M. Rigo, M. Stipulanti, and M. A. Whiteland. Binomial complexities and Parikh-collinear morphisms. In V. Diekert and M. V. Volkov, editors, DLT 2022, volume 13257 of LNCS, 251-262. Springer, 2022. doi:10.1007/978-3-031-05578-2\\_20",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.FL"
  ],
  "abstract": "Two words are $k$-binomially equivalent if each subword of length at most $k$ occurs the same number of times in both words. The $k$-binomial complexity of an infinite word is a counting function that maps $n$ to the number of $k$-binomial equivalence classes represented by its factors of length $n$. Cassaigne et al. [Int. J. Found. Comput. S., 22(4) (2011)] characterized a family of morphisms, which we call Parikh-collinear, as those morphisms that map all words to words with bounded $1$-binomial complexity. Firstly, we extend this characterization: they map words with bounded $k$-binomial complexity to words with bounded $(k+1)$-binomial complexity. As a consequence, fixed points of Parikh-collinear morphisms are shown to have bounded $k$-binomial complexity for all $k$. Secondly, we give a new characterization of Sturmian words with respect to their $k$-binomial complexity. Then we characterize recurrent words having, for some $k$, the same $j$-binomial complexity as the Thue-Morse word for all $j\\le k$. Finally, inspired by questions raised by Lejeune, we study the relationships between the $k$- and $(k+1)$-binomial complexities of infinite words; as well as the link with the usual factor complexity.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2022-12-06T15:37:46.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68R15",
      "05A05",
      "05A10"
    ],
    "keywords": [
      "binomial complexity",
      "characterization",
      "infinite word",
      "usual factor complexity",
      "binomial equivalence classes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 35,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}