Ambiguity and decision problems concerning number systems.

*(English)*Zbl 0541.03006The paper investigates generalized number systems, i.e., the digits may be larger than the base, and completeness is not required: some positive integers may not be representable in terms of the system. The representation is defined exactly as in binary and decimal systems. Apart from the generalized representation theory, such generalized number systems have important applications in the theory of L codes. The paper investigates, in particular, the notions of ambiguity and equivalence for number systems. A number system is ambiguous iff some integer has two representations in terms of the system. Two number systems are equivalent iff the sets of numbers represented in them coincide. The paper shows that both of these properties are decidable. The basic tool (”translation lemma”) is essentially automata-theoretic. Indeed, no purely number- theoretic proof is known for the decidability of the equivalence problem although the problem itself belongs to elementary number theory. The considerations of this paper have recently been extended to concern degrees of ambiguity and number systems with negative digits.

##### MSC:

03B25 | Decidability of theories and sets of sentences |

68Q42 | Grammars and rewriting systems |

11A63 | Radix representation; digital problems |

68Q45 | Formal languages and automata |

03D05 | Automata and formal grammars in connection with logical questions |

94A99 | Communication, information |