References of "Kärki, Tomi"
     in
Bookmark and Share    
Full Text
See detailA characterization of multidimensional S-automatic sequences
Charlier, Emilie ULg; Kärki, Tomi ULg; Rigo, Michel ULg

in Actes des rencontres du CIRM, 1 (2009)

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended ... [more ▼]

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d ≥ 2, we state that a multidimensional infinite word x : N^d → \Sigma over a finite alphabet \Sigma is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲]

Detailed reference viewed: 38 (14 ULg)
Full Text
Peer Reviewed
See detailOn the Recognizability of Self-Generating Sets
Kärki, Tomi ULg; Lacroix, Anne ULg; Rigo, Michel ULg

in Lecture Notes in Computer Science (2009), 5734

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 52 (16 ULg)