References of "Charlier, Emilie"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailInfinite self-shuffling words
Charlier, Emilie ULg

in Journal of Combinatorial Theory - Series A (2014), 128

In this paper we introduce and study a new property of infinite words: An infinite word x, with values in a finite set A, is said to be k-self-shuffling (k≥2) if there exists a shuffle of k copies of x ... [more ▼]

In this paper we introduce and study a new property of infinite words: An infinite word x, with values in a finite set A, is said to be k-self-shuffling (k≥2) if there exists a shuffle of k copies of x which produces x. We are particularly interested in the case k=2, in which case we say x is self-shuffling. This property of infinite words is shown to be independent of the complexity of the word as measured by the number of distinct factors of each length. Examples exist from bounded to full complexity. It is also an intrinsic property of the word and not of its language (set of factors). For instance, every aperiodic word contains a non-self-shuffling word in its shift orbit closure. While the property of being self-shuffling is a relatively strong condition, many important words arising in the area of symbolic dynamics are verified to be self-shuffling. They include for instance the Thue–Morse word fixed by the morphism 0↦01, 1↦10. As another example we show that all Sturmian words of intercept 0<ρ<1 are self-shuffling (while those of intercept ρ=0 are not). Our characterization of self-shuffling Sturmian words can be interpreted arithmetically in terms of a dynamical embedding and defines an arithmetic process we call the stepping stone model. One important feature of self-shuffling words stems from their morphic invariance: The morphic image of a self-shuffling word is self-shuffling. This provides a useful tool for showing that one word is not the morphic image of another. In addition to its morphic invariance, this new notion has other unexpected applications particularly in the area of substitutive dynamical systems. For example, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, on a classification of pure morphic Sturmian words in the orbit of the characteristic. [less ▲]

Detailed reference viewed: 4 (0 ULg)
Full Text
Peer Reviewed
See detailAbelian bordered factors and periodicity
Charlier, Emilie ULg; Harju, Tero; Puzynina, Svetlana et al

in Actes des Journées Montoises d'Informatique Théorique (2014, September)

A finite word is bordered if it has a non-empty proper prefix which is equal to its suffix, and unbordered otherwise. Ehrenfeucht and Silberger proved that an infinite word is (purely) periodic if and ... [more ▼]

A finite word is bordered if it has a non-empty proper prefix which is equal to its suffix, and unbordered otherwise. Ehrenfeucht and Silberger proved that an infinite word is (purely) periodic if and only if it contains only finitely many unbordered factors. We are interested in an abelian modification of this fact. Namely, we have the following question: Let w be an infinite word such that all sufficiently long factors are abelian bordered. Is w (abelian) periodic? We also consider a weakly abelian modification of this question, when only the frequencies of letters are taken into account. Besides that, we answer a question of Avgustinovich, Karhumaki and Puzynina concerning abelian central factorization theorem. [less ▲]

Detailed reference viewed: 4 (1 ULg)
Full Text
Peer Reviewed
See detailThe freeness problem for products of matrices defined on bounded languages
Charlier, Emilie ULg

in Actes des Journées Montoises d'Informatique Théorique (2014, September)

In this talk, I presented a joint work with Juha Honkala. We study the freeness problem for matrix semigroups. We show that the freeness problem is decidable for upper-triangular 2x2 matrices with ... [more ▼]

In this talk, I presented a joint work with Juha Honkala. We study the freeness problem for matrix semigroups. We show that the freeness problem is decidable for upper-triangular 2x2 matrices with rational entries when the products are restricted to certain bounded languages. We also show that this problem becomes undecidable for large enough matrices. [less ▲]

Detailed reference viewed: 4 (0 ULg)
Full Text
Peer Reviewed
See detailThe freeness problem over matrix semigroups and bounded languages
Charlier, Emilie ULg; Honkala, Juha

in Information & Computation (2014), 237

We study the freeness problem for matrix semigroups. We show that the freeness problem is decidable for upper-triangular 2 × 2 matrices with rational entries when the products are restricted to certain ... [more ▼]

We study the freeness problem for matrix semigroups. We show that the freeness problem is decidable for upper-triangular 2 × 2 matrices with rational entries when the products are restricted to certain bounded languages. [less ▲]

Detailed reference viewed: 8 (3 ULg)
Full Text
Peer Reviewed
See detailComposition and orbits of language operations: finiteness and upper bounds
Charlier, Emilie ULg; Domaratzki, Michael; Harju, Tero et al

in International Journal of Computer Mathematics (2013), 90(6), 1171-1196

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are ... [more ▼]

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. If x and y are compositions, we say x is equivalent to y if they have the same effect on all languages L. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any language L under the elements of the monoid is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations. [less ▲]

Detailed reference viewed: 24 (5 ULg)
Full Text
See detailSelf-shuffling words
Charlier, Emilie ULg

Conference (2013, April)

Detailed reference viewed: 16 (3 ULg)
Full Text
Peer Reviewed
See detailSelf-shuffling words
Charlier, Emilie ULg; Kamae, Teturo; Puzynina, Svetlana et al

in Lecture Notes in Computer Science (2013)

In this paper we introduce and study a new property of infinite words which is invariant under the action of a morphism: We say an infinite word x, defined over a finite alphabet A, is self-shuffling if x ... [more ▼]

In this paper we introduce and study a new property of infinite words which is invariant under the action of a morphism: We say an infinite word x, defined over a finite alphabet A, is self-shuffling if x admits factorizations: x=\prod_{i=1}^\infty U_iV_i=\prod_{i=1}^\infty U_i=\prod_{i=1}^\infty V_i with U_i,V_i \in \A^+. In other words, there exists a shuffle of x with itself which reproduces x. The morphic image of any self-shuffling word is again self-shuffling. We prove that many important and well studied words are self-shuffling: This includes the Thue-Morse word and all Sturmian words (except those of the form aC where a is a letter and C is a characteristic Sturmian word). We further establish a number of necessary conditions for a word to be self-shuffling, and show that certain other important words (including the paper-folding word and infinite Lyndon words) are not self-shuffling. In addition to its morphic invariance, which can be used to show that one word is not the morphic image of another, this new notion has other unexpected applications: For instance, as a consequence of our characterization of self-shuffling Sturmian words, we recover a number theoretic result, originally due to Yasutomi, which characterizes pure morphic Sturmian words in the orbit of the characteristic. [less ▲]

Detailed reference viewed: 26 (8 ULg)
See detailAutomates et systèmes de numération
Charlier, Emilie ULg

Conference (2012, August)

Ce cours d'1h30 est accessible à un grand public de mathématiciens, y compris les enseignants du secondaire. Je commencerai par définir ce que sont les automates finis. J'introduirai les systèmes de ... [more ▼]

Ce cours d'1h30 est accessible à un grand public de mathématiciens, y compris les enseignants du secondaire. Je commencerai par définir ce que sont les automates finis. J'introduirai les systèmes de numération en général. Je m'attarderai sur le cas des bases entières, et montrerai les propriétés remarquables de calculs dans ces bases, notamment le calcul de l'addition et de la multiplication par une constante par automate fini. Ensuite, j'étendrai ces considérations à des numérations dites non-standard et aux systèmes de Pisot. Enfin, je définirai les numérations abstraites. [less ▲]

Detailed reference viewed: 20 (5 ULg)
Full Text
See detailA decision problem for ultimate periodicity in non-standard numeration systems
Charlier, Emilie ULg

Conference (2012, July)

In the first part of the talk, I will overview some results on state complexity of ultimately periodic sets in various numeration systems. In the second part of the talk, I will present some applications ... [more ▼]

In the first part of the talk, I will overview some results on state complexity of ultimately periodic sets in various numeration systems. In the second part of the talk, I will present some applications of these methods to the following decidability question: given a DFA recognizing a set of integers represented in a fixed numeration system, decide whether this set is ultimately periodic. The techniques presented in this talk could be extended to other classes of sets of integers, and thus, could be applied to new decidability questions. [less ▲]

Detailed reference viewed: 18 (2 ULg)
Full Text
See detailSyntactical complexity of periodic sets
Charlier, Emilie ULg

Conference (2012, June)

We are interested in the links between numbers and their representations. In the decimal numeration system, a number is even if its representation ends with 0, 2, 4, 6, or 8, which give rise to a simple ... [more ▼]

We are interested in the links between numbers and their representations. In the decimal numeration system, a number is even if its representation ends with 0, 2, 4, 6, or 8, which give rise to a simple representation set, that is, accepted by a finite automaton. More generally, in an integer base numeration system, any divisibility criterion is recognized by a finite automaton. The state complexity of a regular language is the number of states of the minimal automaton accepting this language. The syntactic complexity is the size of the associated syntactical monoid. The first one only takes into account the context on the right side, whereas the second considers both left and right contexts. Given a set of integers, we want to answer the following questions. What is the associated state complexity? What is the associated syntactic complexity? These questions extend to more general numeration systems, as linear numeration systems or abstract numeration systems. Such problems are motivated by decidability problems. For example : given an automaton recognizing a set of integers, decide if this set is ultimately periodic? [less ▲]

Detailed reference viewed: 30 (1 ULg)
Full Text
See detailMonoïde syntaxique et numérations
Charlier, Emilie ULg

Conference (2012, June)

La complexité en nombre d'états (state complexity) d'un langage régulier est le nombre d'états de son automate minimal. La complexité syntaxique est le cardinal du monoïde syntaxique associé. La première ... [more ▼]

La complexité en nombre d'états (state complexity) d'un langage régulier est le nombre d'états de son automate minimal. La complexité syntaxique est le cardinal du monoïde syntaxique associé. La première ne prend en compte que le contexte à droite alors la seconde considère les contextes à gauche et à droite. Nous nous intéressons aux liens entre les nombres et leurs représentations. Dans le système décimal, un nombre est pair si sa représentation se termine par 0, 2, 4, 6 ou 8, ce qui donne lieu à ensemble de représentations simple, c'est-à-dire reconnu par automate. Plus généralement, dans une base entière, tout critère de divisibilité se traduit par un automate. Etant donné un ensemble d'entiers, nous voulons répondre aux questions suivantes. Quel est le nombre d'états de l'automate minimal associé. Quelle est la complexité syntaxique associée ? Ces questions s'étendent à des numérations plus générales. Ces problèmes sont motivés par des problèmes de décidabilité. Par exemple : étant donné un automate reconnaissant un ensemble d'entiers, décider si cet ensemble est ou non ultimement périodique. [less ▲]

Detailed reference viewed: 22 (1 ULg)
Full Text
See detailAn introduction to abstract numeration systems
Charlier, Emilie ULg

Scientific conference (2012, May)

Abstract numeration systems were introduced in 2001 by P. Lecomte and M. Rigo. This new way to represent numbers generalizes that of usual positional numeration systems such as integer base numeration ... [more ▼]

Abstract numeration systems were introduced in 2001 by P. Lecomte and M. Rigo. This new way to represent numbers generalizes that of usual positional numeration systems such as integer base numeration systems and linear numeration systems. Some standard properties are preserved in this wider framework though some others are not. Yet, the advantages of these systems stem from their great generality: current research on this subject strives to highlight the properties that are independent of the target numeration system, such as properties related to the complexity of the numeration language. In this talk I will introduce this topic. In particular, I will present many open questions in the area and highlight the connections with combinatorics on words. [less ▲]

Detailed reference viewed: 37 (1 ULg)
Full Text
See detailAbstract numeration systems
Charlier, Emilie ULg

Scientific conference (2012, May)

Abstract numeration systems were introduced in 2001 by P. Lecomte and M. Rigo. This new way to represent numbers generalizes that of usual positional numeration systems such as integer base numeration ... [more ▼]

Abstract numeration systems were introduced in 2001 by P. Lecomte and M. Rigo. This new way to represent numbers generalizes that of usual positional numeration systems such as integer base numeration systems and linear numeration systems. Some standard properties are preserved in this wider framework though some others are not. Yet, the advantages of these systems stem from their great generality: current research on this subject strives to highlight the properties that are independent of the target numeration system, such as properties related to the complexity of the numeration language. In this talk I will introduce this topic. In particular, I will present many open questions in the area and highlight the connections with combinatorics on words. [less ▲]

Detailed reference viewed: 32 (2 ULg)
See detailEnsembles reconnaissables de rationnels
Charlier, Emilie ULg

Scientific conference (2012, April)

In this talk I will introduce the recognizable sets of rationals, following the formalism of Jeffrey Shallit. I will point out several open questions regarding this topic.

Detailed reference viewed: 6 (0 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

in International Journal of Foundations of Computer Science (2012), 23(5), 1035-1066

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related ... [more ▼]

We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give some new characterizations of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems. [less ▲]

Detailed reference viewed: 13 (7 ULg)
Full Text
Peer Reviewed
See detailMulti-dimensional sets recognizable in all abstract numeration systems
Charlier, Emilie ULg; Lacroix, Anne ULg; Rampersad, Narad ULg

in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications (2012), 46(1), 51-65

We prove that the subsets of N^d that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional ... [more ▼]

We prove that the subsets of N^d that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting. [less ▲]

Detailed reference viewed: 77 (22 ULg)
Full Text
See detailOrbits of language operations: finiteness and upper bounds
Charlier, Emilie ULg

Scientific conference (2011, August)

Detailed reference viewed: 7 (1 ULg)
Full Text
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg

Conference (2011, July)

Detailed reference viewed: 6 (1 ULg)
Full Text
Peer Reviewed
See detailEnumeration and decidable properties of automatic sequences
Charlier, Emilie ULg; Rampersad, Narad; Shallit, Jeffrey

in Actes de Numération 2011 (2011, June)

We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences ... [more ▼]

We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences de ned in terms of Pisot numeration systems. [less ▲]

Detailed reference viewed: 21 (3 ULg)
Full Text
See detailFinite orbits of language operations
Charlier, Emilie ULg

Scientific conference (2011, May)

Detailed reference viewed: 17 (3 ULg)