K-synchronized sequence


In mathematics and theoretical computer science, a k-synchronized sequence is an infinite sequence of terms s 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. 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 k denote the base-k representation of some number n. Given r ≥ 2, a subset R of is k-synchronized if the relation is a right-synchronized rational relation over Σ∗ × ... × Σ∗, where R.

Language-theoretic

Let n ≥ 0 be a natural number and let f: be a map, where both n and f are expressed in base k. The sequence f is k-synchronized if the language of pairs is regular.

History

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

Example

Subword complexity

Given a k-automatic sequence s and an infinite string S = s''s''..., let ρS denote the subword complexity of S; that is, the number of distinct subwords of length n in S. Goč, Schaeffer, and Shallit 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. It then verifies that m is the sum of the sizes of the blocks. Since the pair k is accepted by this automaton, the subword complexity function of the k-automatic sequence s is k-synchronized.

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 is k-automatic if and only if s is k-synchronized and s 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 is a k-synchronized sequence, then both the subword complexity of s and the palindromic complexity of s are k-regular sequences.