×

Automata and numeration systems. (Automates et systèmes de numération.) (French) Zbl 1161.68550

This nice survey paper discusses various number systems from the point of view of formal language theory, by focusing on the connections between arithmetic properties of numbers and syntactic properties of their representations. Questions like the following are addressed throughout this paper: Can we characterize an arithmetic property of an integer \(n\) (such as being divisible by a given integer) by the very representation of \(n\) in the number system?
Prerequisites on formal language theory, such as Chomsky’s hierarchy, are first recalled, with special focus on regular languages and automata theory. Numerations in integer bases are then considered with a discussion on \(k\)-recognizability issues, which leads in a natural way to Cobham’s theorem. This theorem states that the sets of nonnegative integers that are simultaneously \(k\)- and \(l\)-recognizable, for \(k\) and \(l\) multiplicatively independent nonnegative integers, are finite unions of arithmetic progressions. Generalizations to noninteger bases, such as the so-called beta-numeration, are then discussed. This review of classical number systems ends with a further generalization, namely abstract number systems: Assume we are given an arbitrary infinite regular language \(L\) over a totally ordered alphabet; then enumerating the words of \(L\) with respect to the induced genealogical ordering gives a one-to-one correspondence between the set of nonnegative integers and \(L\), and hence a representation map.
Let us note that pertinent bibliographic references are given throughout the text, as are enlightening examples.

MSC:

68Q45 Formal languages and automata
11A63 Radix representation; digital problems
11B85 Automata sequences
68R15 Combinatorics on words
PDFBibTeX XMLCite