Publications
Bookmark and Share    
Full Text
See detailFirst-order Logic and Numeration Systems
Charlier, Emilie ULiege

in Sequences, Groups, and Number Theory (in press)

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: 22 (2 ULiège)
Full Text
See detailPermutations and negative beta-shifts
Charlier, Emilie ULiege; Steiner, Wolfgang

E-print/Working paper (2017)

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: 13 (3 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: 16 (2 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: 16 (2 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: 21 (1 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 & its Applications (2016), 500

Detailed reference viewed: 33 (15 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: 34 (5 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: 55 (12 ULiège)
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: 45 (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: 59 (23 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: 43 (3 ULiège)
Full Text
Peer Reviewed
See detailThe freeness problem for products of matrices defined on bounded languages
Charlier, Emilie ULiege; Honkala, Juha

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: 25 (0 ULiège)
Full Text
Peer Reviewed
See detailAbelian bordered factors and periodicity
Charlier, Emilie ULiege; 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: 18 (1 ULiège)
Full Text
See detailAbelian borders and periodicity
Charlier, Emilie ULiege

Conference (2014, January)

Detailed reference viewed: 15 (1 ULiège)
Full Text
Peer Reviewed
See detailThe freeness problem over matrix semigroups and bounded languages
Charlier, Emilie ULiege; 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: 20 (5 ULiège)
Full Text
Peer Reviewed
See detailComposition and orbits of language operations: finiteness and upper bounds
Charlier, Emilie ULiege; 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: 51 (18 ULiège)
Full Text
See detailSelf-shuffling words
Charlier, Emilie ULiege

Conference (2013, April)

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

in Lecture Notes in Computer Science (2013), 7966

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: 35 (10 ULiège)
See detailAutomates et systèmes de numération
Charlier, Emilie ULiege

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: 36 (5 ULiège)
Full Text
See detailA decision problem for ultimate periodicity in non-standard numeration systems
Charlier, Emilie ULiege

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