zbMATH — the first resource for mathematics

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., ()
[2] Berstel, J., Fibonacci words—A survey, (), 13-27
[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, (), 137-146
[6] Eilenberg, S., ()
[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., ()
[11] de Luca, A.; Restivo, A., Representations of integers and language theory, (), 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.