References of "Charlier, Emilie"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailNyldon words
Charlier, Emilie ULiege; Philibert, Manon; Stipulanti, Manon ULiege

in Journal of Combinatorial Theory. Series A (2019), 167

The Chen-Fox-Lyndon theorem states that every finite word over a fixed alphabet can be uniquely factorized as a lexicographically nonincreasing sequence of Lyndon words. This theorem can be used to define ... [more ▼]

The Chen-Fox-Lyndon theorem states that every finite word over a fixed alphabet can be uniquely factorized as a lexicographically nonincreasing sequence of Lyndon words. This theorem can be used to define the family of Lyndon words in a recursive way. If the lexicographic order is reversed in this definition, we obtain a new family of words, which are called the Nyldon words. In this paper, we show that every finite word can be uniquely factorized into a lexicographically nondecreasing sequence of Nyldon words. Otherwise stated, Nyldon words form a complete factorization of the free monoid with respect to the decreasing lexicographic order. Then we investigate this new family of words. In particular, we show that Nyldon words form a right Lazard set. [less ▲]

Detailed reference viewed: 27 (12 ULiège)
Full Text
Peer Reviewed
See detailRecurrence in multidimensional words
Charlier, Emilie ULiege; Puzynina, Svetlana; Vandomme, Elise ULiege

in Lecture Notes in Computer Science (2019), 11417

In this paper we study various modifications of the notion of uniform recurrence in multidimensional infinite words. A d-dimensional infinite word is said to be uniformly recurrent if for each prefix ... [more ▼]

In this paper we study various modifications of the notion of uniform recurrence in multidimensional infinite words. A d-dimensional infinite word is said to be uniformly recurrent if for each prefix, there exists a fixed size such that each block of this size contains the prefix. We introduce and study a new notion of uniform recurrence of multidimensional infinite words: for each rational slope, each rectangular prefix must occur along this slope with bounded gaps. Such words are called uniformly recurrent along all directions. We provide several constructions of multidimensional infinite words satisfying this condition, and more generally, a series of three conditions on recurrence. We study general properties of these new notions and in particular we study the strong uniform recurrence of fixed points of square morphisms. [less ▲]

Detailed reference viewed: 36 (10 ULiège)
Full Text
See detailNyldon words
Charlier, Emilie ULiege

Conference (2018, February)

The theorem of Chen-Fox-Lyndon states that every finite word can be uniquely factorized as a nonincreasing sequence of Lyndon words with respect to the lexicographic order. This theorem can be used to ... [more ▼]

The theorem of Chen-Fox-Lyndon states that every finite word can be uniquely factorized as a nonincreasing sequence of Lyndon words with respect to the lexicographic order. This theorem can be used to define the family of Lyndon words in a recursive way: 1) the letters are Lyndon; 2) a finite word of length greater than one is Lyndon if it cannot be factorized into a nonincreasing sequence of shorter Lyndon words. In a post on Mathoverflow in November 2014, Darij Grinberg defines a variant of Lyndon words, which he calls Nyldon words, by reversing the lexicographic order in the previous recursive definition. The class of words so obtained is not, as one might first think, the class of maximal words in their conjugacy classes. Gringberg asks three questions: 1) How many Nyldon words of length n are there? 2) Is there an equivalent to the Chen-Fox-Lyndon theorem for Nyldon words? 3) Is it true that every primitive words admits exactly one Nyldon word in his conjugacy class? In this talk, I will discuss these questions in the more general context of Lazard factorizations of the free monoid and show that each of Grinberg’s questions has an explicit answer. This is a joint work with Manon Philibert (ENS Lyon) and Manon Stipulanti (ULiège) [less ▲]

Detailed reference viewed: 18 (2 ULiège)
Full Text
See detailNyldon words
Charlier, Emilie ULiege

in Actes des 17èmes Journées Montoises d'Informatique Théorique (2018)

The theorem of Chen-Fox-Lyndon states that every finite word can be uniquely factorized as a nonincreasing sequence of Lyndon words with respect to the lexicographic order. This theorem can be used to ... [more ▼]

The theorem of Chen-Fox-Lyndon states that every finite word can be uniquely factorized as a nonincreasing sequence of Lyndon words with respect to the lexicographic order. This theorem can be used to define the family of Lyndon words in a recursive way: 1) the letters are Lyndon; 2) a finite word of length greater than one is Lyndon if it cannot be factorized into a nonincreasing sequence of shorter Lyndon words. In a post on Mathoverflow in November 2014, Darij Grinberg defines a variant of Lyndon words, which he calls Nyldon words, by reversing the lexicographic order in the previous recursive definition. The class of words so obtained is not, as one might first think, the class of maximal words in their conjugacy classes. Gringberg asks three questions: 1) How many Nyldon words of length n are there? 2) Is there an equivalent to the Chen-Fox-Lyndon theorem for Nyldon words? 3) Is it true that every primitive words admits exactly one Nyldon word in his conjugacy class? In this talk, I will discuss these questions in the more general context of Lazard factorizations of the free monoid and show that each of Grinberg’s questions has a positive answer. This is a joint work with Manon Philibert (ENS Lyon) and Manon Stipulanti (ULiège). [less ▲]

Detailed reference viewed: 14 (0 ULiège)
Full Text
Peer Reviewed
See detailPermutations and negative beta-shifts
Charlier, Emilie ULiege; Steiner, Wolfgang

in International Journal of Foundations of Computer Science (2018), 29(5), 721-740

Elizalde (2011) characterized which permutations can be obtained by ordering consecutive elements in the trajectories of (positive) beta-transformations and beta-shifts. We prove similar results for ... [more ▼]

Elizalde (2011) characterized which permutations can be obtained by ordering consecutive elements in the trajectories of (positive) beta-transformations and beta-shifts. We prove similar results for negative bases beta. [less ▲]

Detailed reference viewed: 37 (11 ULiège)
Full Text
See detailFirst-order Logic and Numeration Systems
Charlier, Emilie ULiege

in Sequences, Groups, and Number Theory (2018)

The Büchi-Bruyère theorem states that a multidimensional set of non-negative integers is b-recognizable if and only if it is b-definable. This result is a powerful tool for showing that many properties of ... [more ▼]

The Büchi-Bruyère theorem states that a multidimensional set of non-negative integers is b-recognizable if and only if it is b-definable. This result is a powerful tool for showing that many properties of b-automatic sequences are decidable. Going a step further, first-order logic can be used to show that many enumeration problems of b-automatic sequences can be described by b-regular sequences. The latter sequences can be viewed as a generalization of b-automatic sequences to integer-valued sequences. These techniques were extended to two wider frameworks: U-recognizable multidimensional sets of non-negative integers and multidimensional beta-recognizable sets of reals. In the second case, real numbers are represented by infinite words, and hence, the notion of beta-recognizability is defined by means of Büchi automata. Again, logic-based characterizations of $U$-recognizable (resp. beta-recognizable) sets allows us to obtain various decidability results. The aim of this chapter is to present a survey of this very active research domain. [less ▲]

Detailed reference viewed: 41 (9 ULiège)
Full Text
See detailMATh.en.JEANS
Charlier, Emilie ULiege; Ernst, Marie ULiege; Esser, Céline ULiege et al

Book published by MATh.en.JEANS.be (2018)

Ce livre recueille 6 articles écrits par 20 élèves ayant participé à l'initiative MeJ.be en 2016-2017, ainsi qu'un descriptif du congrès organisé à Liège au mois d’avril 2017 durant lequel ces mêmes ... [more ▼]

Ce livre recueille 6 articles écrits par 20 élèves ayant participé à l'initiative MeJ.be en 2016-2017, ainsi qu'un descriptif du congrès organisé à Liège au mois d’avril 2017 durant lequel ces mêmes participants sont venus présenter leurs résultats, en compagnie de près de 300 autres jeunes venus de Belgique, de France et du Luxembourg. Dans ces quelques pages vous découvrirez, chers lecteurs, des problèmes simples à poser mais qui ouvrent des portes vers des trésors de réflexion et vous aurez l’occasion de suivre le raisonnement de jeunes adolescents qui les ont abordé avec très peu d’outils à leur disposition. A la fin de ce livre vous serez également amenés à faire un autre constat à contre-pied de celui qui est souvent fait de nos jours : nos jeunes sont formidables et, pour peu que nous parvenions à nourrir leurs compétences et les amener à s’épanouir, l’avenir de notre espèce est radieux, grâce à eux. [less ▲]

Detailed reference viewed: 61 (12 ULiège)
See detailSpecial issue dedicated to the 16th "Journées Montoises d'Informatique Théorique"
Charlier, Emilie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

Book published by EDP Sciences (2018)

Detailed reference viewed: 31 (7 ULiège)
Full Text
See detailPermutation groups and the Morse-Hedlund Theorem
Charlier, Emilie ULiege

Conference (2017, September)

In this talk I presented the results of the paper "On a group theoretic generalization of the Morse-Hedlund theorem", which is a joint work with Svetlana Puzynina and Luca Zamboni. In this paper, we give ... [more ▼]

In this talk I presented the results of the paper "On a group theoretic generalization of the Morse-Hedlund theorem", which is a joint work with Svetlana Puzynina and Luca Zamboni. In this paper, we give a broad unified framework via group actions for constructing complexity functions of infinite words. Factor complexity, Abelian complexity and cyclic complexity are all particular cases of this general construction. [less ▲]

Detailed reference viewed: 32 (4 ULiège)
See detailPreface
Charlier, Emilie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

in Developments in Language Theory (2017)

Detailed reference viewed: 17 (4 ULiège)
See detailDevelopments in Language Theory
Charlier, Emilie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

Book published by Springer (2017)

The series of international conferences on Developments in Language Theory provides a forum for presenting current developments in formal languages and automata. Its scope is very general and includes ... [more ▼]

The series of international conferences on Developments in Language Theory provides a forum for presenting current developments in formal languages and automata. Its scope is very general and includes, among others, the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors and transducers for strings, trees, graphs, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and analysis; polyominoes and bidimensional patterns; cryptography; concurrency; cellular automata; bio-inspired computing; quantum computing. The papers submitted to DLT 2017 were from 19 countries including Belgium, Canada, Czech Republic, France, Germany, Hungary, India, Italy, Japan, The Netherlands, Poland, Portugal, Republic of Korea, Russia, Slovakia, South Africa, Thailand and USA. [less ▲]

Detailed reference viewed: 40 (4 ULiège)
Full Text
Peer Reviewed
See detailOn a group theoretic generalization of the Morse-Hedlund theorem
Charlier, Emilie ULiege; Puzynina, Svetlana; Zamboni, Luca

in Proceedings of the American Mathematical Society (2017), 145(8), 33813394

In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word contains at least n+ 1 distinct factors of each length n. They further showed that an infinite ... [more ▼]

In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word contains at least n+ 1 distinct factors of each length n. They further showed that an infinite word has exactly n+ 1 distinct factors of each length n if and only if it is binary, aperiodic and balanced, i.e., it is a Sturmian word. In this paper we obtain a broad generalization of the Morse-Hedlund theorem via group actions. [less ▲]

Detailed reference viewed: 23 (3 ULiège)
Full Text
See detailLogic, Decidability and Numeration Systems
Charlier, Emilie ULiege

Conference (2016, November)

The theorem of Büchi-Bruyère states that a subset of N^d is b-recognizable if and only if it is b-definable. As a corollary, the first-order theory of (N,+,V_b) is decidable (where V_b(n) is the largest ... [more ▼]

The theorem of Büchi-Bruyère states that a subset of N^d is b-recognizable if and only if it is b-definable. As a corollary, the first-order theory of (N,+,V_b) is decidable (where V_b(n) is the largest power of the base b dividing n). This classical result is a powerful tool in order to show that many properties of b-automatic sequences are decidable. The first part of my lecture will be devoted to presenting this result and its applications to b-automatic sequences. Then I will move to b-regular sequences, which can be viewed as a generalization of b-automatic sequences to integer-valued sequences. I will explain how first-order logic can be used to show that many enumeration problems of b-automatic sequences give rise to corresponding b-regular sequences. Finally, I will consider more general frameworks than integer bases and (try to) give a state of the art of the research in this domain. [less ▲]

Detailed reference viewed: 31 (4 ULiège)
Full Text
Peer Reviewed
See detailAsymptotic properties of free monoid morphisms
Charlier, Emilie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

in Linear Algebra and its Applications (2016), 500

Detailed reference viewed: 51 (16 ULiège)
Full Text
Peer Reviewed
See detailPermutations and negative beta-shifts
Charlier, Emilie ULiege; Steiner, Wolfgang

in Actes de Numeration 2016 (2016, May)

Elizalde (2011) characterized which permutations can be obtained by ordering consecutive elements in the trajectories of (positive) beta-transformations and beta-shifts. We prove similar results for ... [more ▼]

Elizalde (2011) characterized which permutations can be obtained by ordering consecutive elements in the trajectories of (positive) beta-transformations and beta-shifts. We prove similar results for negative bases beta. [less ▲]

Detailed reference viewed: 42 (6 ULiège)
Full Text
Peer Reviewed
See detailPermutations and shifts
Charlier, Emilie ULiege

in Lecture Notes in Computer Science (2016), 9840

The entropy of a symbolic dynamical system is usually defined in terms of the growth rate of the number of distinct allowed factors of length $n$. Bandt, Keller and Pompe showed that, for piecewise ... [more ▼]

The entropy of a symbolic dynamical system is usually defined in terms of the growth rate of the number of distinct allowed factors of length $n$. Bandt, Keller and Pompe showed that, for piecewise monotone interval maps, the entropy is also given by the number of permutations defined by consecutive elements in the trajectory of a point. This result is the starting point of several works of Elizalde where he investigates permutations in shift systems, notably in full shifts and in beta-shifts. The goal of this talk is to survey Elizalde's results. I will end by mentioning the case of negative beta-shifts, which has been simultaneously studied by Elizalde and Moore on the one hand, and by Steiner and myself on the other hand. [less ▲]

Detailed reference viewed: 58 (15 ULiège)
Full Text
Peer Reviewed
See detailAbelian bordered factors and periodicity
Charlier, Emilie ULiege; Harju, Tero; Puzynina, Svetlana et al

in European Journal of Combinatorics (2016), 51

A finite word u is said to be bordered if u has a proper prefix which is also a suffix of u, and unbordered otherwise. Ehrenfeucht and Silberger proved that an infinite word is purely periodic if and only ... [more ▼]

A finite word u is said to be bordered if u has a proper prefix which is also a suffix of u, 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 abelian and weak abelian analogues of this result; namely, we investigate the following question(s): Let w be an infinite word such that all sufficiently long factors are (weakly) abelian bordered; is w (weakly) abelian periodic? In the process we answer a question of Avgustinovich et al. concerning the abelian critical factorization theorem. [less ▲]

Detailed reference viewed: 49 (13 ULiège)
Full Text
Peer Reviewed
See detailAn analogue of Cobham's theorem for graph directed iterated function systems
Charlier, Emilie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

in Advances in Mathematics (2015), 280

Feng and Wang showed that two homogeneous iterated function systems in $\mathbb{R}$ with multiplicatively independent contraction ratios necessarily have different attractors. In this paper, we extend ... [more ▼]

Feng and Wang showed that two homogeneous iterated function systems in $\mathbb{R}$ with multiplicatively independent contraction ratios necessarily have different attractors. In this paper, we extend this result to graph directed iterated function systems in $\mathbb{R}^n$ with contraction ratios that are of the form $\frac{1}{\beta}$, for integers $\beta$. By using a result of Boigelot {\em et al.}, this allows us to give a proof of a conjecture of Adamczewski and Bell. In doing so, we link the graph directed iterated function systems to Büchi automata. In particular, this link extends to real numbers $\beta$. We introduce a logical formalism that permits to characterize sets of $\mathbb{R}^n$ whose representations in base $\beta$ are recognized by some Büchi automata. This result depends on the algebraic properties of the base: $\beta$ being a Pisot or a Parry number. The main motivation of this work is to draw a general picture representing the different frameworks where an analogue of Cobham's theorem is known. [less ▲]

Detailed reference viewed: 63 (25 ULiège)
Full Text
Peer Reviewed
See detailInfinite self-shuffling words
Charlier, Emilie ULiege; Kamae, Teturo; Puzynina, Svetlana et al

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: 20 (3 ULiège)