{
  "id": "2012.04969",
  "version": "v1",
  "published": "2020-12-09T10:49:21.000Z",
  "updated": "2020-12-09T10:49:21.000Z",
  "title": "Regular sequences and synchronized sequences in abstract numeration systems",
  "authors": [
    "Émilie Charlier",
    "Célia Cisternino",
    "Manon Stipulanti"
  ],
  "comment": "38 pages, 13 figures",
  "categories": [
    "math.CO",
    "cs.DM",
    "cs.FL",
    "math.AC"
  ],
  "abstract": "The notion of $b$-regular sequences was generalized to abstract numeration systems by Maes and Rigo in 2002. Their definition is based on a notion of $\\mathcal{S}$-kernel that extends that of $b$-kernel. However, this definition does not allow us to generalize all of the many characterizations of $b$-regular sequences. In this paper, we present an alternative definition of $\\mathcal{S}$-kernel, and hence an alternative definition of $\\mathcal{S}$-regular sequences, which enables us to use recognizable formal series in order to generalize most (if not all) known characterizations of $b$-regular sequences to abstract numeration systems. We then give two characterizations of $\\mathcal{S}$-automatic sequences as particular $\\mathcal{S}$-regular sequences. Next, we present a general method to obtain various families of $\\mathcal{S}$-regular sequences by enumerating $\\mathcal{S}$-recognizable properties of $\\mathcal{S}$-automatic sequences. As an example of the many possible applications of this method, we show that, provided that addition is $\\mathcal{S}$-recognizable, the factor complexity of an $\\mathcal{S}$-automatic sequence defines an $\\mathcal{S}$-regular sequence. In the last part of the paper, we study $\\mathcal{S}$-synchronized sequences. Along the way, we prove that the formal series obtained as the composition of a synchronized relation and a recognizable series is recognizable. As a consequence, the composition of an $\\mathcal{S}$-synchronized sequence and a $\\mathcal{S}$-regular sequence is shown to be $\\mathcal{S}$-regular. All our results are presented in an arbitrary dimension $d$ and for an arbitrary semiring $\\mathbb{K}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-12-09T10:49:21.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q45",
      "11B85",
      "11A67",
      "13F25"
    ],
    "keywords": [
      "regular sequence",
      "abstract numeration systems",
      "synchronized sequence",
      "formal series",
      "recognizable"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 38,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}