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).
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
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
[2] Given a k-automatic sequence s(n) and an infinite string S = s(1)s(2)..., let ρS(n) denote the subword complexity of S; that is, the number of distinct subwords of length n in S. Goč, Schaeffer, and Shallit[3] demonstrated that there exists a finite automaton accepting the language This automaton guesses the endpoints of every contiguous block of symbols in S and verifies that each subword of length n starting within a given block is novel while all other subwords are not.
Since the pair (n, m)k is accepted by this automaton, the subword complexity function of the k-automatic sequence s(n) is k-synchronized.