Numeration Systems, Linear Recurrences, and Regular Sets

A numeration system based on a strictly increasing sequence of positive integers u 0 = 1, u 1, u 2, .. . expresses a non-negative integer n as a sum n = ∑i j = 0 a j u j. In this case we say the string a i a i − 1···a 1 a 0 is a representation for n. If gcd(u 0, u 1, .. .) = g, then every sufficiently large multiple of g has some representation. If the lexicographic ordering on the representations is the same as the usual ordering of the integers, we say the numeration system is order-preserving. In particular, if u 0 = 1, then the greedy representation, obtained via the greedy algorithm, is order-preserving. We prove that, subject to some technical assumptions, if the set of all representations in an order-preserving numeration system is regular, then the sequence u = (u j ) j ≥ 0 satisfies a linear recurrence. The converse, however, is not true. The proof uses two lemmas about regular sets that may be of independent interest. The first shows that if L is regular, then the set of lexicographically greatest strings of every length in L is also regular. The second shows that the number of strings of length n in a regular language L is bounded by a constant (independent of n) iff L is the finite union of sets of the form xy*z.

Authors

• J. Shallit

Keywords

No keywords are indexed for this paper.