Structure of the minimal automaton of a numeration language and applications to state complexity

We study the structure of automata accepting the greedy representations of N in a
wide class of numeration systems. We describe the conditions under which such automata can
have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand
numeration system. Furthermore, we show that for any automaton A arising from a system
with a dominant root > 1, there is a morphism mapping A onto the automaton arising from
the Bertrand system associated with the number . Under some mild assumptions, we also
study the state complexity of the trim minimal automaton accepting the greedy representations
of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the
number of states of the trim minimal automaton accepting the greedy representations of mN in
the Fibonacci system is exactly 2m^2.