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

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


68Q45 Formal languages and automata
11B37 Recurrences
11A63 Radix representation; digital problems
Full Text: DOI


[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
[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
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.