Discrete Mathematics & Theoretical Computer Science, Vol 13, No 1 (2011)

Font Size:  Small  Medium  Large

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