Abstract
Odometers or "adding machines" are usually introduced in the context of positional numeration systems built on a strictly increasing sequence of integers. We generalize this notion to systems defined on an arbitrary infinite regular language. In this latter situation, if (A,<) is a totally ordered alphabet, then enumerating the words of a regular language L over A with respect to the induced genealogical ordering gives a one-to-one correspondence between ℕ and L. In this general setting the odometer is not defined on a set of sequences of digits but on a set of pairs of sequences where the first (resp. the second) component of the pair is an infinite word over A (resp. an infinite sequence of states of the minimal automaton of L). We study some properties of the odometer such as continuity, injectivity, surjectivity, minimality, .... We then study some particular cases: we show the equivalence of this new function with the classical odometer built upon a sequence of integers whenever the set of greedy representations of all the integers is a regular language; we also consider substitution numeration systems as well as the connection with β-numerations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Berthé, V., Rigo, M. Odometers on Regular Languages. Theory Comput Syst 40, 1–31 (2007). https://doi.org/10.1007/s00224-005-1215-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-005-1215-5