On subtrees of the representation tree in rational base numeration systems

zbMATH Open1434.11022arXiv1706.08266MaRDI QIDQ4560233FDOQ4560233

Authors: Shigeki Akiyama, Victor Marsault, Jacques Sakarovitch 

Publication date: 10 December 2018

Abstract: Every rational number p/q defines a rational base numeration system in which every integer has a unique finite representation, up to leading zeroes. This work is a contribution to the study of the set of the representations of integers. This prefix-closed subset of the free monoid is naturally represented as a highly non-regular tree. Its nodes are the integers, its edges bear labels taken in {0,1,...,p-1}, and its subtrees are all distinct. We associate with each subtree (or with its root n) three infinite words. The bottom word of n is the lexicographically smallest word that is the label of a branch of the subtree. The top word of n is defined similarly. The span-word of n is the digitwise difference between the latter and the former. First, we show that the set of all the span-words is accepted by an infinite automaton whose underlying graph is essentially the same as the tree itself. Second, we study the function that computes for all n the bottom word associated with n+1 from the one associated with n, and show that it is realised by an infinite sequential transducer whose underlying graph is once again essentially the same as the tree itself. An infinite word may be interpreted as an expansion in base p/q after the radix point, hence evaluated to a real number. If T is a subtree whose root is n, then the evaluations of the labels of the branches of T form an interval of $mathbbR$. The length of this interval is called the span of n and is equal to the evaluation of the span-word of n. The set of all spans is then a subset of R and we use the preceding construction to study its topological closure. We show that it is an interval when p is greater than or equal to 2q-1, and a Cantor set of measure zero otherwise.

Full work available at URL: https://arxiv.org/abs/1706.08266

Recommendations

• Auto-similarity in rational base number systems
• Trees and languages with periodic signature
• On sets of numbers rationally represented in a rational base number system
• Bertrand numeration systems and recognizability
• Linear numeration systems and \(\theta\)-representations

zbMATH Keywords

Cantor setsHausdorff measureinfinite wordsrational base numeration systemsinfinite transducersreal-representation tree

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Other number representations (11A67)

Cited In (4)

• Auto-similarity in rational base number systems
• Breadth-first serialisation of trees and rational languages (short paper)
• Pm numbers, ambiguity, and regularity
• Trees and languages with periodic signature

This page was built for publication: On subtrees of the representation tree in rational base numeration systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4560233)