K-synchronized sequence

Not to be confused with Synchronizing word.

In mathematics and theoretical computer science, a k-synchronized sequence is an infinite sequence of terms s(n) characterized by a finite automaton taking as input two strings m and n, each expressed in some fixed base k, and accepting if m = s(n). The class of k-synchronized sequences lies between the classes of k-automatic sequences and k-regular sequences.

Definitions

As relations

Let Σ be an alphabet of k symbols where k ≥ 2, and let [n]_k denote the base-k representation of some number n. Given r ≥ 2, a subset R of $\mathbb {N} ^{r}$ is k-synchronized if the relation {([n₁]_k, ..., [n_r]_k)} is a right-synchronized rational relation over Σ^∗ × ... × Σ^∗, where (n₁, ..., n_r) $\in$ R.

Language-theoretic

Let n ≥ 0 be a natural number and let f: $\mathbb {N} \rightarrow \mathbb {N}$ be a map, where both n and f(n) are expressed in base k. The sequence f(n) is k-synchronized if the language of pairs $\{(n,f(n))\}$ is regular.

History

The class of k-synchronized sequences was introduced by Carpi and Maggi.

Properties

k-synchronized sequences exhibit a number of interesting properties. A non-exhaustive list of these properties is presented below.

• Every k-synchronized sequence is k-regular.
• Every k-automatic sequence is k-synchronized. To be precise, a sequence s(n) is k-automatic if and only if s(n) is k-synchronized and s(n) takes on finitely many terms. This is an immediate consequence of both the above property and the fact that every k-regular sequence taking on finitely many terms is k-automatic.
• The class of k-synchronized sequences is closed under termwise sum and termwise composition.
• The terms of any k-synchronized sequence have a linear growth rate.
• If s(n) is a k-synchronized sequence, then both the subword complexity of s(n) (the number of distinct subwords of each length of the infinite word S = s(1)s(2)...) and the palindromic complexity of s(n) (likewise, for distinct palindromes) are k-regular sequences.

References

• Carpi, A.; Maggi, C. (2010), "On synchronized sequences and their separators", Theoret. Informatics Appl., 35: 513–524, doi:10.1051/ita:2001129.