• Images
• Videos
• Documents
• Books
• Articles

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 N r {\displaystyle \mathbb {N} ^{r}} is k-synchronized if the relation {([n1]k, ..., [nr]k)} is a right-synchronized¹ rational relation over Σ∗ × ... × Σ∗, where (n1, ..., nr) ∈ {\displaystyle \in } R.²

Language-theoretic

Let n ≥ 0 be a natural number and let f: N → N {\displaystyle \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 ) ) } {\displaystyle \{(n,f(n))\}} 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

{ ( n , m ) k ∣ n ≥ 0  and  m = ρ S ( n ) } . {\displaystyle \{(n,m)_{k}\mid n\geq 0{\text{ and }}m=\rho _{S}(n)\}.}

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.⁵
• 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) and the palindromic complexity of s(n) (similar to subword complexity, but for distinct palindromes) are k-regular sequences.¹⁰

Notes

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

References

1. Frougny, C.; Sakarovitch, J. (1993), "Synchronized rational relations of finite and infinite words", Theoret. Comput. Sci., 108: 45–82, doi:10.1016/0304-3975(93)90230-Q /wiki/Doi_(identifier) ↩

2. Carpi & Maggi (2010) ↩

3. Carpi & Maggi (2010) ↩

4. Goč, D.; Schaeffer, L.; Shallit, J. (2013). Subword complexity and k-synchronization. Lecture Notes in Computer Science. Vol. 7907. Editors Béal MP., Carton O. Berlin: Springer. ISBN 978-3-642-38770-8. 978-3-642-38770-8 ↩

5. Carpi & Maggi (2010), Proposition 2.6 ↩

6. Carpi & Maggi (2010), Proposition 2.8 ↩

7. Carpi & Maggi (2010), Proposition 2.1 ↩

8. Carpi & Maggi (2010), Proposition 2.2 ↩

9. Carpi & Maggi (2010), Proposition 2.5 ↩

10. Carpi, A.; D'Alonzo, V. (2010), "On factors of synchronized sequences", Theoret. Comput. Sci., 411 (44–46): 3932–3937, doi:10.1016/j.tcs.2010.08.005 /wiki/Doi_(identifier) ↩