Numeration systems; Confluence; Alternate base; Rewriting systems
Abstract :
[en] We study normalisation as a rewriting system in the framework of two-way alternate bases.
In this framework, nonnegative real numbers are represented by right-infinite words with a decimal point.
A number may have multiple representations, among which one is distinguished unsing a greedy algorithm and called the expansion. The problem of normalisation is to find, given a word, the expansion of the number it represents.
We study this problem by seeing normalisation as a rewriting system, taking a representation as input and iteratively rewriting factors which cannot appear in expansions while keeping the value of the word constant, until the expansion is reached.
We are especially interested in the numeration systems for which this associated rewriting system is confluent, that is, two words that can be obtained by rewriting a common start word can in turn be rewritten as a common end word.
We obtain a characterisation of those systems: up to technicalities, all but the last digit in any expansion of 1 must be maximal.
A connection is made to the problem of the equality between the spectrum and the integers of a numeration system. This problem asks whether all numbers that admit a representation only to the left of the fractional point also have their expansion only to the left of the fractional point.
Using a similar framework of rewriting rules, we find a class of systems where this equality is reached, with a criterion similar in statement to the one mentioned above.
