Ambiguity and decision problems concerning number systems. (English) Zbl 0541.03006

Culik, Karel II; Salomaa, Arto

Inf. Control 56, 139-153 (1983).

The 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

Keywords:

cryptography; L systems; generalized number systems; completeness; L codes; ambiguity; equivalence; decidability