NUMERATION SYSTEMS, LINEAR RECURRENCES, AND REGULAR SETS

A numeration system based on a strictly increasing sequence of positiv e integers u0 = u1, u2, ... expresses a non-negative integer n as a su m n = SIGMA(j=0)i a(j)u(j). In this case we say the string a(i)a(i-1) ... a1a0 is a representation for n. If gcd(u0, u1, ...) = g, then ever y sufficiently large multiple of g has some representation. If the lex icographic ordering on the representations is the same as the usual or dering of the integers, we say the numeration system is order-preservi ng. In particular, if u0 = 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 a n order-preserving numeration system is regular, then the sequence u = (u(j))j greater-than-or-equal-to 0 satisfies a linear recurrence. The converse, however, is not true. The proof uses two lemmas about regul ar sets that may be of independent interest. The first shows that if L is regular, then the set of lexicographically greatest strings of eve ry length in L is also regular. The second shows that the number of st rings of length n in a regular language L is bounded by a constant (in dependent of n) iff L is the finite union of sets of the form xyz. (C ) 1994 Academic Press, Inc.