sontag@control.rutgers.edu (Eduardo Sontag) (06/21/91)
Assume that a0,a1,a2,a3,... is a binary sequence.
It is classical and easy to prove that the following are equivalent:
(1) The series a0 + a1 x + a2 x^2 + ... is rational over Q (or Z)
(2) This series is rational over Z_2
(3) The set {n | an = 0} is a recognizable subset of N (seen as {x}*, free
monoid in one letter)
Let nQ, n2 be the sizes of the minimal recursion in the first two cases
respectively, and nA the size of the smallest automaton in case 3.
It is easy to see that
n2 <= nQ <= nA
for every sequence, and the numbers may be distinct.
The QUESTION is: does anyone have any reference to estimates of how large the
gaps between these numbers may be?
I haven't seen any such estimates in any of the obvious references (Eilenberg,
Salomaa-Soittola, Berstel-Reutenauer...). The answer may very well be trivial;
I just haven't thought enough about the problem.
Thanks!
-eduardo
PS: Please e-mail me a copy of any posting; I don't read the bboards often
enough...
--
Eduardo D. Sontag
Department of Mathematics
Rutgers Center for Systems and Control (SYCON)
Rutgers University
New Brunswick, NJ 08903, USA
(Phone: (908)932-3072; dept.: (908)932-2390)
sontag@hilbert.rutgers.edu