Linear numeration systems of order two. (English) Zbl 0648.68066

Frougny, Christiane

Inf. Comput. 77, No. 3, 233-259 (1988).

The author considers a numeration system \((U_ v,s)\) of the form \[ u_{n+2}=au_{n+1}+bu_ n,\quad u_ 0=1,\quad u_ 1=v\geq 2\quad. \] He shows that the system is complete only if \(v=a+1\) and \(s=a\). For the system \((U_{a+1},a)\) there exists a uniquely defined normal form of a word which may be computed by a composition of two subsequential machines. Addition of integers represented in \((U_{a+1},a)\) may be computed by a left-subsequential machine.

Reviewer: M.Frumkin

MSC:

68Q45	Formal languages and automata
11B37	Recurrences
11A63	Radix representation; digital problems

Keywords:

numeration system; subsequential machines

References:

[1]	Berstel, J., (Transductions and Context-Free Languages (1979), Teubner: Teubner Stuttgart) · Zbl 0424.68040
[2]	Berstel, J., Fibonacci words—A survey, (The Book of \(L (1986)\), Springer-Verlag: Springer-Verlag Berlin/New York), 13-27 · Zbl 0589.68053
[3]	Carlitz, L., Fibonacci representations, Fibonacci Quart., 6, 4, 193-220 (1968) · Zbl 0167.03901
[4]	Choffrut, Ch., Une caractérisation des fonctions séquentielles et des fonctions sous-séquentielles en tant que relations rationnelles, Theoret. Comput. Sci., 5, 325-337 (1977) · Zbl 0376.94022
[5]	Culik, K.; Salomaa, A., Ambiguity and decision problems concerning number systems, (Lecture Notes in Computer Science, Vol. 154 (1983), Springer-Verlag: Springer-Verlag Berlin/New York), 137-146 · Zbl 0582.10004
[6]	Eilenberg, S., (Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[7]	Fraenkel, A. S., Systems of numeration, Amer. Math. Monthly, 92, 2, 105-114 (1985) · Zbl 0568.10005
[8]	Honkala, J., Bases and ambiguity of number systems, Theoret. Comput. Sci., 31, 61-71 (1984) · Zbl 0546.68066
[9]	Huet, G., Confluent reductions: Abstract properties and applications to term rewriting systems, J. Assoc. Comput. Mach., 27, 797-821 (1980) · Zbl 0458.68007
[10]	Knuth, D. E., (The Art of Computer Programming, Vols. 1,2, and 3 (1975), Addison-Wesley: Addison-Wesley Reading, MA)
[11]	de Luca, A.; Restivo, A., Representations of integers and language theory, (Lecture Notes in Computer Science, Vol. 176 (1984), Springer-Verlag: Springer-Verlag Berlin/New York), 407-415 · Zbl 0584.68083
[12]	Sakarovitch, J., Easy multiplications, Inform. and Comput., 74, 3, 173-197 (1987) · Zbl 0642.20043
[13]	Zeckendorf, E., Representation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège, 3-4, 179-182 (1972) · Zbl 0252.10011