On number systems with negative digits. (English) Zbl 0659.68098

Honkala, Juha

Ann. Acad. Sci. Fenn., Ser. A I, Math. 14, No. 1, 149-156 (1989).

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\) are integers. Negative digits are allowed. The word \(m_{i_ 0}...m_{i_ k}\) represents the integer \(m_{i_ 0}n^ k+...+m_{i_ k}\). The set of represented nonnegative integers is denoted by PosS(N). We show that PosS(N) is n-recognizable. The degree of ambiguity of a number system N is 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\). We show that the degree of a given number system can be computed effectively. We show also that it is decidable whether or not \(PosS(N_ 1)=PosS(N_ 2)\) if \(N_ 1\) and \(N_ 2\) are given number systems.

Reviewer: J.Honkala

MSC:

68T99	Artificial intelligence
11A63	Radix representation; digital problems

Keywords:

decidability; degree of ambiguity; number systems