On-line finite automata for addition in some numeration systems
Frougny, Christiane
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999), p. 79-101 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1999-01-01
@article{ITA_1999__33_1_79_0,
     author = {Frougny, Christiane},
     title = {On-line finite automata for addition in some numeration systems},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {33},
     year = {1999},
     pages = {79-101},
     mrnumber = {1705857},
     zbl = {0927.68052},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1999__33_1_79_0}
}

Frougny, Christiane. On-line finite automata for addition in some numeration systems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 33 (1999) pp. 79-101. http://gdmltest.u-ga.fr/item/ITA_1999__33_1_79_0/

[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. | MR 1432196 | Zbl 0870.68105

[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. | MR 135213

[4] M. P. Béal, Codage symbolique, Masson (1993).

[5] J. Berstel, Transductions and Context-free Languages, Teubner (1979). | MR 549481 | Zbl 0424.68040

[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. | Zbl 0589.68053

[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. | MR 504457 | Zbl 0376.94022

[10] J. Duprat, Y. Herreros and S. Kla, New redundant representations of complex numbers and vectors. IEE Trans. Comput. C-42 (1993) 817-824. | MR 1252310

[11] S. Eilenberg, Automata, languages and machines, Vol. A (Academic Press, 1974). | MR 530382 | Zbl 0317.94045

[12] M. D. Ercegovac, On-line arithmetic: An overview. Real time Signal Processing VII SPIE 495 (1984) 86-93.

[13] Ch. Frougny, Confluent linear numeration systems. Theoret. Comput. Sci. 106 (1992) 183-219. | MR 1192767 | Zbl 0787.68057

[14] Ch. Frougny, Representation of numbers and finite automata. Math. Systems Theory 25 (1992) 37-60. | MR 1139094 | Zbl 0776.11005

[15] Ch. Frougny, Parallel and on-line addition in negative base and some complex number systems, in Proc. of the Conference Euro-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. | MR 1490563 | Zbl 1015.68128

[17] W. Gilbert, Radix representations of quadratic field. J. Math. Anal. Appl. 83 (1981) 264-274. | MR 632342 | Zbl 0472.10011

[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. | MR 389759 | Zbl 0297.12003 | Zbl 0309.12001

[20] D. E. Knuth, An imaginary number system. CACM 3 (1960) 245-247. | MR 127508

[21] D. E. Knuth, The art of computer programming, Seminumerical Algorithms, Vol. 2, 2nd ed. (Addison-Wesley, 1988). | MR 378456

[22] S. Körmendi, Classical number systems in Q[3√2]. Acta Sci. Math. 50 (1986) 351-357. | Zbl 0616.10007

[23] D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University Press (1995). | MR 1369092 | Zbl 1106.37301

[24] D. W. Matula, Basic digit sets for radix representation. JACM 29 (1982) 1131-1143. | MR 674260 | Zbl 0509.10008

[25] J.-M. Muller, Some characterizations of fonctions computable in on-line arithmetic. IEE Trans. Comput. 43 (1994) 752-755. | MR 1284161 | Zbl 1042.68503

[26] A. M. Nielsen and J.-M. Muller, Borrow-save adders for real and complex number systems, in Proc. of the Conference Real Numbers and Computers, Marseille (1996) 121-137.

[27] K. Pekmestzi, Complex numbers multipliers. IEE Proc. Computers and Digital Techniques 136 (1989) 70-75.

[28] W. Penney, A "binary" system for complex numbers. JACM 12 (1965) 247-248. | Zbl 0127.08803

[29] A. Rényi, Representations for real numbers and their ergodic properties. Acta Math. Acad. Sci. Hungar. 8 (1957) 477-493. | MR 97374 | Zbl 0079.08901

[30] A. Robert, A good basis for computing with complex numbers. El. Math. 49 (1994) 111-117. | MR 1286599 | Zbl 0813.30001

[31] T. Safer, Radix representations of algebraic number fields and finite automata, in Proc. Stacs'98, LNCS 1373 (1998) 356-365. | MR 1650694 | Zbl 0919.11009

[32] K. S. Trivedi and M. D. Ercegovac, On-line algorithms for division and multiplication. IEE Trans. Comput. C 26 (1977) 681-687. | MR 451846 | Zbl 0406.68040

[33] O. Vaysse, Addition molle et fonctions p-locales. Semigroup Forum 34 (1986) 157-175. | MR 868252 | Zbl 0605.68070