''k''-regular sequence

In mathematics and theoretical computer science, a k-regular sequence is an infinite sequence of terms characterized by a finite automaton with auxiliary storage.^[1] They are a generalization of k-automatic sequences to alphabets of infinite size.

Definition

There exist several characterizations of k-regular sequences, all of which are equivalent. Some common characterizations are as follows. For each, we take R′ to be a commutative Noetherian ring and we take R to be a ring containing R′.

k-kernel

Let k ≥ 2. The k-kernel of the sequence s(n) is the set of subsequences

K_{k}(s)=\{s(k^{e}n+r):e\geq 0{\text{ and }}0\leq r\leq k^{e}-1\}.

The sequence s(n) is (R′, k)-regular (often shortened to just "k-regular") if K_k(s) is a sub-module of a finitely-generated R′-module.^[2]

Linear combinations

A sequence s(n) is k-regular if there exists an integer E such that, for all e_j > E and 0 ≤ r_j ≤ k^e_j − 1, every subsequence of s of the form s(k^e_jn + r_j) is expressible as an R′-linear combination $\sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})$ , where c_ij is an integer, f_ij ≤ E, and 0 ≤ b_ij ≤ k^f_ij − 1.^[3]

Alternatively, a sequence s(n) is k-regular if there exist an integer r and subsequences s₁(n), ..., s_r(n) such that, for all 1 ≤ i ≤ r and 0 ≤ a ≤ k − 1, every sequence s_i(kn + a) in the k-kernel K_k(s) is an R′-linear combination of the subsequences s_i(n).^[3]

Formal series

Let x₀, ..., x_k − 1 be a set of k non-commuting variables and let τ be a map sending some natural number n to the string x_a₀ ... x_{a_e − 1}, where the base-k representation of x is the string a_e − 1...a₀. Then a sequence s(n) is k-regular if and only if the formal series $\sum _{n\geq 0}s(n)\tau (n)$ is $\mathbb {Z}$ -rational.^[4]

Automata-theoretic

The formal series definition of a k-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.^[1]^[5]

History

The notion of k-regular sequences was first investigated in a pair of papers by Allouche and Shallit.^[6] Prior to this, Berstel and Reutenauer studied the theory of rational series, which is closely related to k-regular sequences.^[7]

Examples

Thue–Morse sequence

The Thue–Morse sequence t(n) ( A010060) is the fixed point of the morphism 0 → 01, 1 → 10. It is known that the Thue–Morse sequence is 2-automatic. Thus, it is also 2-regular, and its 2-kernel

\{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}

consists of the subsequences $t(n)_{n\geq 0}$ and $t(2n+1)_{n\geq 0}$ .

Ruler sequence

Let h(n) = ν₂(n + 1) be the 2-adic valuation of n + 1. The ruler sequence h(n) ( A007814) is 2-regular, and the 2-kernel

\{h(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}

is contained in the two-dimensional vector space generated by h(n) and the constant sequence $1,1,1,\dots$ . These basis elements lead to the recurrence relations

{\begin{aligned}h(2n)&=0,\\h(4n+1)&=h(2n+1)-s(n),\\h(4n+3)&=2h(2n+1)-s(n),\end{aligned}}

which, along with the initial conditions h(0) = 0 and h(1) = 1, uniquely determine the sequence.^[8]

Cantor numbers

The sequence of Cantor numbers c(n) ( A005823) consists of numbers whose ternary expansions contain no 1s. It is straightforward to show that

{\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}

and therefore the sequence of Cantor numbers is 2-regular.^[9]

Merge sort

A somewhat interesting application of the notion of k-regularity to the broader study of algorithms is found in the analysis of the merge sort algorithm. Given a list of n values, the number of comparisons made by the merge sort algorithm is governed by the recurrence relation

{\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}

As a result, the sequence defined by the recurrence relation for merge sort, T(n), constitutes a 2-regular sequence.^[10]

Other sequences

If $f(x)$ is an integer-valued polynomial, then $f(n)_{n\geq 0}$ is k-regular for every $k\geq 2$ .

Allouche and Shallit give a number of additional examples of k-regular sequences in their papers.^[6]

Properties

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

Every k-automatic sequence is k-regular.^[11]
A k-regular sequence takes on finitely many values if and only if it is k-automatic.^[12] This is an immediate consequence of the class of k-regular sequences being a generalization of the class of k-automatic sequences.
The class of k-regular sequences is closed under termwise addition, termwise multiplication, and convolution. The class of k-regular sequences is also closed under scaling each term of the sequence by an integer λ.^[12]^[13]^[14]^[15]
For multiplicatively independent k, l ≥ 2, if a sequence is both k-regular and l-regular, then the sequence satisfies a linear recurrence.^[16] This is a generalization of a result due to Cobham regarding sequences that are both k-automatic and l-automatic.^[17]

Notes

1 2 Allouche & Shallit (1992), Theorem 4.4
↑ Allouche & Shallit (1992), Definition 2.1
1 2 Allouche & Shallit (1992), Theorem 2.2
↑ Allouche & Shallit (1992), Theorem 4.3
↑ Schützenberger, M.-P. (1961), "On the definition of a family of automata", Information and Control, 4: 245–270, doi:10.1016/S0019-9958(61)80020-X .
1 2 Allouche & Shallit (1992, 2003)
↑ Berstel, Jean; Reutenauer, Christophe (1988). Rational Series and Their Languages. EATCS Monographs on Theoretical Computer Science. 12. Springer-Verlag. ISBN 978-3-642-73237-9.
↑ Allouche & Shallit (1992), Example 8
↑ Allouche & Shallit (1992), Example 3
↑ Allouche & Shallit (1992), Example 28
↑ Allouche & Shallit (1992), Theorem 2.3
1 2 Allouche & Shallit (2003) p. 441
↑ Allouche & Shallit (1992), Theorem 2.5
↑ Allouche & Shallit (1992), Theorem 3.1
↑ Allouche & Shallit (2003) p. 445
↑ Bell, J. (2006). "A generalization of Cobham’s theorem for regular sequences". Seminaire Lotharingien de Combinatoire. 54A.
↑ Cobham, A. (1969). "On the base-dependence of sets of numbers recognizable by finite automata". Math. Systems Theory. 3 (2): 186–192. doi:10.1007/BF01746527.

References

Allouche, Jean-Paul; Shallit, Jeffrey (1992), "The ring of k-regular sequences", Theoret. Comput. Sci., 98: 163–197, doi:10.1016/0304-3975(92)90001-v .
Allouche, Jean-Paul; Shallit, Jeffrey (2003), "The ring of k-regular sequences, II", Theoret. Comput. Sci., 307: 3–29, doi:10.1016/s0304-3975(03)00090-2 .
Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.