On-line finite automata for addition in some numeration systems

Christiane Frougny

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 33, Issue: 1, page 79-101
  • ISSN: 0988-3754

Abstract

top
We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base β and addition in base βm is given. Results on addition in base β = b m , where b is a relative integer, follow. We also show that addition in base the golden ratio is computable by an on-line finite automaton, but is not parallelizable.

How to cite

top

Frougny, Christiane. "On-line finite automata for addition in some numeration systems." RAIRO - Theoretical Informatics and Applications 33.1 (2010): 79-101. <http://eudml.org/doc/222083>.

@article{Frougny2010,
abstract = { We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base β and addition in base βm is given. Results on addition in base $\beta=\sqrt[m]\{b\}$, where b is a relative integer, follow. We also show that addition in base the golden ratio is computable by an on-line finite automaton, but is not parallelizable. },
author = {Frougny, Christiane},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {numeration systems},
language = {eng},
month = {3},
number = {1},
pages = {79-101},
publisher = {EDP Sciences},
title = {On-line finite automata for addition in some numeration systems},
url = {http://eudml.org/doc/222083},
volume = {33},
year = {2010},
}

TY - JOUR
AU - Frougny, Christiane
TI - On-line finite automata for addition in some numeration systems
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 1
SP - 79
EP - 101
AB - We consider numeration systems where the base is a negative integer, or a complex number which is a root of a negative integer. We give parallel algorithms for addition in these numeration systems, from which we derive on-line algorithms realized by finite automata. A general construction relating addition in base β and addition in base βm is given. Results on addition in base $\beta=\sqrt[m]{b}$, where b is a relative integer, follow. We also show that addition in base the golden ratio is computable by an on-line finite automaton, but is not parallelizable.
LA - eng
KW - numeration systems
UR - http://eudml.org/doc/222083
ER -

References

top
  1. J.-P. Allouche, E. Cateland, W.J. Gilbert, H.-O. Peitgen, J.O. Shallit and G. Skordev, Automatic maps in exotic numeration systems. Theory Comput. Syst.30 (1997) 285-331.  
  2. T. Aoki, H. Amada and T. Higuchi, Real/complex reconfigurable arithmetic using redundant complex number systems, in Proc. 13th Symposium on Computer Arithmetic (1997) 200-207.  
  3. A. Avizienis, Signed-digit number representations for fast parallel arithmetic. IEE Trans. Electron. Comput.10 (1961) 389-400.  
  4. M.P. Béal, Codage symbolique, Masson (1993).  
  5. J. Berstel, Transductions and Context-free Languages, Teubner (1979).  
  6. J. Berstel, Fonctions rationnelles et addition. Actes de l'École de Printemps de Théorie des Langages, LITP (1982) 177-183.  
  7. J. Berstel, Fibonacci words -- A survey, The book of L, Springer-Verlag (1986) 13-27.  
  8. C.Y. Chow and J.E. Robertson, Logical design of a redundant binary adder, in Proc. 4th Symposium on Computer Arithmetic (1978) 109-115.  
  9. C. Choffrut, Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles. Theoret. Comput. Sci.5 (1977) 325-337.  
  10. J. Duprat, Y. Herreros and S. Kla, New redundant representations of complex numbers and vectors. IEE Trans. Comput.C-42 (1993) 817-824.  
  11. S. Eilenberg, Automata, languages and machines, Vol. A (Academic Press, 1974).  
  12. M.D. Ercegovac, On-line arithmetic: An overview. Real time Signal Processing VIISPIE 495 (1984) 86-93.  
  13. Ch. Frougny, Confluent linear numeration systems. Theoret. Comput. Sci.106 (1992) 183-219.  
  14. Ch. Frougny, Representation of numbers and finite automata. Math. Systems Theory25 (1992) 37-60.  
  15. Ch. Frougny, Parallel and on-line addition in negative base and some complex number systems, in Proc. of the ConferenceEuro-Par 96, Springer, Lyon, L.N.C.S.1124 (1996) 175-182.  
  16. Ch. Frougny and J. Sakarovitch, Synchronisation déterministe des automates à délai borné. Theoret. Comput. Sci.191 (1998) 61-77.  
  17. W. Gilbert, Radix representations of quadratic fields. J. Math. Anal. Appl.83 (1981) 264-274.  
  18. Y. Herreros, Contribution à l'arithmétique des ordinateurs, Ph.D. Dissertation, I.N.P.G., Grenoble, France (1991).  
  19. I. Kátai and J. Szabó, Canonical number systems. Acta Sci. Math.37 (1975) 255-280.  
  20. D.E. Knuth, An imaginary number system. CACM3 (1960) 245-247.  
  21. D.E. Knuth, The art of computer programming, Seminumerical Algorithms, Vol. 2, 2nd ed. (Addison-Wesley, 1988).  
  22. S. Körmendi, Classical number systems in Q [ 2 3 ] .Acta Sci. Math.50 (1986) 351-357.  
  23. D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press (1995).  
  24. D.W. Matula, Basic digit sets for radix representation. JACM29 (1982) 1131-1143.  
  25. J.-M. Muller, Some characterizations of functions computable in on-line arithmetic. IEE Trans. Comput.43 (1994) 752-755.  
  26. A.M. Nielsen and J.-M. Muller, Borrow-save adders for real and complex number systems, in Proc. of the ConferenceReal Numbers and Computers, Marseille (1996) 121-137.  
  27. K. Pekmestzi, Complex numbers multipliers. IEE Proc. Computers and Digital Techniques136 (1989) 70-75.  
  28. W. Penney, A ``binary" system for complex numbers. JACM12 (1965) 247-248.  
  29. A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar.8 (1957) 477-493.  
  30. A. Robert, A good basis for computing with complex numbers. El. Math.49 (1994) 111-117.  
  31. T. Safer, Radix representations of algebraic number fields and finite automata, in Proc. Stacs'98, LNCS1373 (1998) 356-365.  
  32. K.S. Trivedi and M.D. Ercegovac, On-line algorithms for division and multiplication. IEE Trans. Comput.C 26 (1977) 681-687.  
  33. O. Vaysse, Addition molle et fonctions p-locales. Semigroup Forum34 (1986) 157-175.  

NotesEmbed ?

top

You must be logged in to post comments.