Skip to Main content Skip to Navigation
Journal articles

Odometers on Regular Languages

Valerie Berthe 1 Michel Rigo 2
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Odometers or "adding machines" are usually introduced in the context of positional numeration systems built on a strictly increasing sequenceof 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 N 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 like 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 BETA-numerations.
Document type :
Journal articles
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00130835
Contributor : Valerie Berthe <>
Submitted on : Tuesday, February 27, 2007 - 12:19:45 PM
Last modification on : Thursday, May 24, 2018 - 3:59:21 PM
Long-term archiving on: : Tuesday, April 6, 2010 - 10:29:13 PM

File

Identifiers

  • HAL Id : lirmm-00130835, version 1

Collections

Citation

Valerie Berthe, Michel Rigo. Odometers on Regular Languages. Theory of Computing Systems, Springer Verlag, 2007, 40, pp.001-031. ⟨lirmm-00130835⟩

Share

Metrics

Record views

159

Files downloads

181