Reference : On the Recognizability of Self-Generating Sets
Scientific congresses and symposiums : Paper published in a journal
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/15863
On the Recognizability of Self-Generating Sets
English
Kärki, Tomi [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Lacroix, Anne mailto [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 >]
2009
Lecture Notes in Computer Science
Springer
5734
34th International Symposium: Mathematical Foundations of Computer Science
525-536
Yes
International
0302-9743
1611-3349
Berlin
Germany
34th International Symposium: Mathematical Foundations of Computer Science
Novy Smokovec, High Tatras
Slovakia
[en] numeration system ; self-generating set ; Cobham's theorem ; automatic sequences ; syndeticity
[en] Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of integers containing I and satisfying f(X)\subseteq X for all f in F. In particular, solving a conjecture of Allouche, Shallit and Skordev, we show under some technical conditions that if two of the constants k_i are multiplicatively independent, then X is not k-recognizable for any k>=2.
Researchers
http://hdl.handle.net/2268/15863

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Restricted access
sg4.pdfAuthor preprint154.57 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.