Reference : The minimal automaton recognizing mN in a linear numeration system
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Engineering, computing & technology : Computer science
http://hdl.handle.net/2268/82571
The minimal automaton recognizing mN in a linear numeration system
English
Charlier, Emilie mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Rampersad, Narad [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Waxweiler, Laurent [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
2011
Integers: Electronic Journal of Combinatorial Number Theory
11B
A4
Proceedings of the Leiden Numeration Conference 2010
1-24
Yes
International
1553-1732
[en] Numeration System ; Bertrand System ; Beta-expansion ; State Complexity ; Parry Number ; Finite Automaton
[en] We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>1 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2.
http://hdl.handle.net/2268/82571
http://www.integers-ejcnt.org/vol11b.html

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
CRRW-final-integers.pdfAuthor postprint223.77 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.