Digit set conversion by on-line finite automata
Athasit Surarerks · Bulletin of the Belgian Mathematical Society - Simon Stevin · 2001
This paper is about numbers represented in positional notation, in integral or complex bases. We first give an abstract scheme of an on-line algorithm for digit set conversion in fixed base. Then we prove that in positive or negative integral base the digit set conversion is computable by an on-line finite state automaton. We also show similar results for complex numbers represented in the Penney number system or in the Knuth number system. Resume Ce papier porte sur les nombres en notation positionnelle selon une base qui peut etre un nombre entier ou complexe. Nous donnons d’abord un schema abstrait d’algorithme en-ligne realisant la conversion en base fixe entre alphabets de chiffres differents. Ensuite nous prouvons qu’en base entiere, positive ou negative, la conversion est realisable par un automate fini en-ligne. Enfin nous montrons des resultats similaires pour les nombres complexes representes dans le systeme de numeration de Penney et le systeme de numeration de Knuth.