K-synchronized Sequence

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''sub>''k'' denote the base-''k'' representation of some number ''n''. Given ''r'' ≥ 2, a subset ''R'' of $\mathbb^$ is ''k''-synchronized if the relation is a right-synchronized rational relation over Σ^∗ × ... × Σ^∗, where (''n''₁, ..., ''n''_''r'') $\in$ ''R''.Carpi & Maggi (2010)

Language-theoretic

Let ''n'' ≥ 0 be a natural number and let ''f'': $\mathbb \rightarrow \mathbb$ 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 $\$ is regular.

History

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

Example

Subword complexity

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 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 (''n'', ''m'')_''k'' is accepted by this automaton, the subword complexity function of the ''k''-automatic sequence ''s''(''n'') 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.Carpi & Maggi (2010), Proposition 2.6
*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.Carpi & Maggi (2010), Proposition 2.8 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.Carpi & Maggi (2010), Proposition 2.1Carpi & Maggi (2010), Proposition 2.2
*The terms of any ''k''-synchronized sequence have a linear growth rate.Carpi & Maggi (2010), Proposition 2.5
*If ''s''(''n'') is a ''k''-synchronized sequence, then both the subword complexity of ''s''(''n'') and the palindromic complexity of ''s''(''n'') (similar to subword complexity, but for distinct palindromes) are ''k''-regular sequences.

Notes

References

*{{citation , last1 = Carpi , first1 = A. , last2 = Maggi , first2 = C. , title = On synchronized sequences and their separators , journal = Theoret. Informatics Appl. , volume = 35 , issue = 6 , year = 2010 , pages = 513–524 , doi=10.1051/ita:2001129 , url = http://www.numdam.org/item/ITA_2001__35_6_513_0/ .

Sequences and series