Bases and ambiguity of number systems. (English) Zbl 0546.68066

Honkala, Juha

Theor. Comput. Sci. 31, 61-71 (1984).

A number system is a \((v+1)-\)tuple \(N=(n,m_ 1,...,m_ v)\) where \(n\geq 2,\) \(v\geq 1\) and \(m_ 1,...,m_ v\geq 1.\) The word \(m_{i_ 0}...m_{i_ k}\) represents the integer \(m_{i_ 0}\cdot n^ k+...+m_{i_ k}.\) The set of represented integers is denoted by S(N). An integer b is called a base of S(N) if there exists a number system \(N_ 1=(b,a_ 1,...,a_ u)\) such that \(S(N)=S(N_ 1)\). We show that the bases of S(N) form a subfamily of an exponential family if S(N) is not a finite union of arithmetic progressions. If the set S(N) has arbitrarily long gaps, then S(N) has only one base. The degree of ambiguity of a number N is defined to be the greatest integer p such that some integer has p representations and none has more than p representations. If there is no such integer the degree of N is \(\infty\). The degree of S(N) equals q if there is a number system M of degree q such that \(S(N)=S(M)\) and there is no number system M’ of degree lower than q such that \(S(N)=S(M')\). We show that all degrees of ambiguity do exist and that the degree of a given number system can be computed effectively.

MSC:

68Q45	Formal languages and automata
11A63	Radix representation; digital problems
68Q42	Grammars and rewriting systems

Keywords:

number system; represented integers; base; degree of ambiguity

References:

[1]	Cobham, A., On the base-dependence of sets of numbers recognizable by finite automata, Math. Systems Theory, 3, 186-192 (1969) · Zbl 0179.02501
[2]	Culik, K.; Salomaa, A., Ambiguity and decision problems concerning number systems, (Tech. Rept. CS-82-14, 154 (1983), Springer: Springer Berlin), 137-146, University of Waterloo; a shortened version in: Lecture Notes in Compouter Science
[3]	Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[4]	Maurer, H.; Salomaa, A.; Wood, D., L codes and number systems, Theoret. Comput. Sci., 22, 331-346 (1983) · Zbl 0531.68027
[5]	Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025