Bases and ambiguity of number systems.

*(English)*Zbl 0546.68066A 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 |

Full Text:
DOI

##### 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, (), 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 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 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.