Afficher la notice abrégée

dc.contributor.authorCharlier, Émilie
dc.contributor.authorRampersad, Narad
dc.contributor.authorRigo, Michel
dc.contributor.authorWaxweiler, Laurent
dc.date.accessioned2018-03-16T15:32:48Z
dc.date.available2018-03-16T15:32:48Z
dc.date.issued2011-12-02
dc.identifier.citationÉ. Charlier, N. Rampersad, M. Rigo, L. Waxweiler, “The minimal automaton recognizing mN in a linear numeration system”, Integers 11B (2011), A4.en_US
dc.identifier.issn1867-0652
dc.identifier.urihttp://hdl.handle.net/10680/1412
dc.description.abstractWe 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 β > 1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number β. Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m ≥ 2 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 2m2.en_US
dc.language.isoenen_US
dc.publisherIntegersen_US
dc.rightsinfo:eu-repo/semantics/openAccess
dc.titleThe minimal automaton recognizing mN in a linear numeration systemen_US
dc.typeArticleen_US


Fichier(s) constituant ce document

Thumbnail

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée