Bases and ambiguity of number systems
type: Item
instance of: scholarly article
title: Bases and ambiguity of number systems
zbMATH Open document ID: 0546.68066
DOI: 10.1016/0304-3975(84)90126-9
author: Juha Honkala
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 11A63
Mathematics Subject Classification ID: 68Q42
zbMATH DE Number: 3870630
zbMATH Keywords: number system
zbMATH Keywords: represented integers
zbMATH Keywords: base
zbMATH Keywords: degree of ambiguity
MaRDI profile type: Publication
full work available at URL: 0304-3975(84)90126-9
OpenAlex ID: W1973057672
cites work: On the base-dependence of sets of numbers recognizable by finite automata
cites work: Q3705510
cites work: Q4079524
cites work: L codes and number systems
cites work: Q5678435
Recommended article: Ambiguity and decision problems concerning number systems
Recommended article: Q3705510
Recommended article: On number systems with finite degree of ambiguity
Recommended article: Q4339624
Recommended article: Alternate Base Numeration Systems
Recommended article: Systems of Numeration
Recommended article: Q3335844
Recommended article: Q3236733
Recommended article: Two-base numeration systems
description: scientific article; zbMATH DE number 3870630