“K-regular sequence”的意思、由来-开放百科全书

In mathematics and theoretical computer science, a k-regular sequence is a sequence satisfying linear recurrence equations that reflect the base-k representations of the integers. The class of k-regular sequences generalizes the class 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

The sequence

is (R′, k)-regular (often shortened to just "k-regular") if the

-module generated by K_k(s) is a finitely-generated R′-module.^[1]

In the special case when

, the sequence

-regular if

is contained in a finite-dimensional vector space over

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

, where c_ij is an integer, f_ij ≤ E, and 0 ≤ b_ij ≤ k^f_ij − 1.^[2]

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).^[2]

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

-rational.^[3]

Automata-theoretic

The formal series definition of a k-regular sequence leads to an automaton characterization similar to Schützenberger's matrix machine.^[4]^[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

Ruler sequence

Let

be the

-adic valuation of

. The ruler sequence

({{OEIS2C|id=A007814}}) is

-regular, and the

-kernel

is contained in the two-dimensional vector space generated by

and the constant sequence

. These basis elements lead to the recurrence relations

which, along with the initial conditions

and

, uniquely determine the sequence.^[8]

Thue–Morse sequence

The Thue–Morse sequence t(n) ({{OEIS2C|id=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

Cantor numbers

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

and therefore the sequence of Cantor numbers is 2-regular. Similarly the Stanley sequence

Sorting numbers

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 are the sorting numbers, governed by the recurrence relation

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

Other sequences

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

Properties

Notes

1. ^Allouche & Shallit (1992), Definition 2.1
2. ^¹Allouche & Shallit (1992), Theorem 2.2
3. ^Allouche & Shallit (1992), Theorem 4.3
4. ^Allouche & Shallit (1992), Theorem 4.4
5. ^{{citation | last = Schützenberger | first = M.-P. | title = On the definition of a family of automata | journal = Information and Control | volume = 4 | issue = 2–3 | year = 1961 | pages = 245–270 | doi=10.1016/S0019-9958(61)80020-X }}.
6. ^¹Allouche & Shallit (1992, 2003)
7. ^{{cite book | last1 = Berstel | first1 = Jean | last2 = Reutenauer | first2 = Christophe | title = Rational Series and Their Languages | volume = 12 | series = EATCS Monographs on Theoretical Computer Science | year = 1988 | isbn = 978-3-642-73237-9 | publisher = Springer-Verlag }}
8. ^Allouche & Shallit (1992), Example 8
9. ^Allouche & Shallit (1992), Examples 3 and 26
10. ^Allouche & Shallit (1992), Example 28
11. ^Allouche & Shallit (1992), Theorem 2.3
12. ^¹Allouche & Shallit (2003) p. 441
13. ^Allouche & Shallit (1992), Theorem 2.5
14. ^Allouche & Shallit (1992), Theorem 3.1
15. ^Allouche & Shallit (2003) p. 445
16. ^{{cite journal | first=J. | last=Bell | title=A generalization of Cobham's theorem for regular sequences| journal=Séminaire Lotharingien de Combinatoire | volume=54A | year=2006 }}
17. ^{{cite journal | first=A. | last=Cobham | title=On the base-dependence of sets of numbers recognizable by finite automata | journal=Math. Systems Theory | volume=3 | issue=2 | year=1969 | pages=186–192 | doi=10.1007/BF01746527 }}
18. ^Allouche & Shallit (1992) Theorem 2.10