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

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.


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


[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
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.