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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.