Negative bases and automata
Christiane Frougny, Anna Chiara Lai
Abstract
We study expansions in non-integer negative base -β introduced by
Ito and Sadahiro. Using countable automata associated with
(-β)-expansions, we characterize the case where the (-β)-shift
is a system of finite type. We prove that, if beta is a Pisot number,
then the (-β)-shift is a sofic system. In that case, addition (and
more generally normalization on any alphabet) is realizable by a
finite transducer. We then give an on-line algorithm for the
conversion from positive base beta to negative base -β. When β
is a Pisot number, the conversion can be realized by a finite on-line
transducer.
Full Text: PDF PostScript