Article (Scientific journals)
Odometers on regular languages
Berthé; Rigo, Michel
2007In Theory of Computing Systems, 40 (1), p. 1-31
Peer Reviewed verified by ORBi
 

Files


Full Text
vbmr.pdf
Author preprint (290.21 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Odometer; regular language; continuous map; infinite word
Abstract :
[en] 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 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 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 beta-numerations.
Disciplines :
Mathematics
Computer science
Author, co-author :
Berthé
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Odometers on regular languages
Publication date :
January 2007
Journal title :
Theory of Computing Systems
ISSN :
1432-4350
eISSN :
1433-0490
Publisher :
Springer, New York, United States - New York
Volume :
40
Issue :
1
Pages :
1-31
Peer reviewed :
Peer Reviewed verified by ORBi
Commentary :
The original publication is available at www.springerlink.com
Available on ORBi :
since 10 December 2008

Statistics


Number of views
59 (6 by ULiège)
Number of downloads
2 (2 by ULiège)

Scopus citations®
 
9
Scopus citations®
without self-citations
4
OpenCitations
 
7

Bibliography


Similar publications



Contact ORBi