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

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


68T99 Artificial intelligence
11A63 Radix representation; digital problems
Full Text: DOI

Online Encyclopedia of Integer Sequences:

a(1)=1, and if x is a term then 3x-1 and 3x+2 are terms too.