On-line finite automata for addition in some numeration systems

被引：14

作者：

Frougny, C

机构：

[1] Univ Paris 08, F-75251 Paris 05, France

[2] LIAFA, F-75251 Paris, France

来源：

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS | 1999年 / 33卷 / 01期

关键词：

D O I：

10.1051/ita:1999107

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 automate. A general construction relating addition in base beta and addition in base beta(m) is given. Results on addition in base beta = (m)root 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.

引用

页码：79 / 101

页数：23

共 33 条

[1]

Allouche JP, 1997, THEOR COMPUT SYST, V30, P285

[2]

[Anonymous], INTRO SYMBOLIC DYNAM

[3] Real/complex reconfigurable arithmetic using redundant complex number systems [J].

Aoki, T ;

Amada, H ;

Higuchi, T .

13TH IEEE SYMPOSIUM ON COMPUTER ARITHMETIC, PROCEEDINGS, 1997, :200-207

[4]

Avizienis A, 1961, IRE Trans Electron Comput EC, VEC-10, P389, DOI DOI 10.1109/TEC.1961.5219227

[5]

BEAL MP, 1993, CODAGE SYMBOLIQUE

[6]

BERSTEL J, 1982, ACTES ECOLE PRINTEMP, P177

[7]

Berstel J., 1979, TEUBNER STUDIENBUCHE, V38

[8]

Choffrut C., 1977, Theoretical Computer Science, V5, P325, DOI 10.1016/0304-3975(77)90049-4

[9]

Chow C. Y., 1978, Proceedings of the 4th Symposium on Computer Arithmetic, P109

[10] NEW REDUNDANT REPRESENTATIONS OF COMPLEX NUMBERS AND VECTORS [J].

DUPRAT, J ;

HERREROS, Y ;

KLA, S .

IEEE TRANSACTIONS ON COMPUTERS, 1993, 42 (07) :817-824

← 1 2 3 4 →