Source author record

Emilie Charlier

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Discrete Mathematics math.CO math.DS math.NT

Catalog footprint

Research overview

8works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Asymptotic properties of free monoid morphisms

Motivated by applications in the theory of numeration systems and recognizable sets of integers, this paper deals with morphic words when erasing morphisms are taken into account. Cobham showed that if an infinite word $w =g(f^ω(a))$ is the image of a fixed point of a morphism $f$ under another morphism $g$ , then there exist a non-erasing morphism $σ$ and a coding $τ$ such that $w =τ(σ^ω(b))$ . Based on the Perron theorem about asymptotic properties of powers of non-negative matrices, our main contribution is an in-depth study of the growth type of iterated morphisms when one replaces erasing morphisms with non-erasing ones. We also explicitly provide an algorithm computing $σ$ and $τ$ from $f$ and $g$ .

preprint2015arXiv

Abelian bordered factors and periodicity

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.

preprint2015arXiv

On a group theoretic generalization of the Morse-Hedlund theorem

In their 1938 seminal paper on symbolic dynamics, Morse and Hedlund proved that every aperiodic infinite word $x\in A^N,$ over a non empty finite alphabet $A,$ contains at least $n+1$ distinct factors of each length $n.$ They further showed that an infinite word $x$ has exactly $n+1$ distinct factors of each length $n$ if and only if $x$ is binary, aperiodic and balanced, i.e., $x$ is a Sturmian word. In this paper we obtain a broad generalization of the Morse-Hedlund theorem via group actions. Given a subgroup $G$ of the symmetric group $S_n,$ let $1\leq ε(G)\leq n$ denote the number of distinct $G$ -orbits of $\{1,2,\ldots ,n\}.$ Since $G$ is a subgroup of $S_n,$ it acts on $A^n=\{a_1a_2\cdots a_n\,|\,a_i\in A\}$ by permutation. Thus, given an infinite word $x\in A^N$ and an infinite sequence $ω=(G_n)_{n\geq 1}$ of subgroups $G_n \subseteq S_n,$ we consider the complexity function $p_{ω,x}:N \rightarrow N$ which counts for each length $n$ the number of equivalence classes of factors of $x$ of length $n$ under the action of $G_n.$ We show that if $x$ is aperiodic, then $p_{ω, x}(n)\geqε(G_n)+1$ for each $n\geq 1,$ and moreover, if equality holds for each $n,$ then $x$ is Sturmian. Conversely, let $x$ be a Sturmian word. Then for every infinite sequence $ω=(G_n)_{n\geq 1}$ of Abelian subgroups $G_n \subseteq S_n,$ there exists $ω'=(G_n')_{n\geq 1}$ such that for each $n\geq 1:$ $G_n'\subseteq S_n$ is isomorphic to $G_n$ and $p_{ω',x}(n)=ε(G'_n)+1.$ Applying the above results to the sequence $(Id_n)_{n\geq 1},$ where $Id_n$ is the trivial subgroup of $S_n$ consisting only of the identity, we recover both directions of the Morse-Hedland theorem.

preprint2013arXiv

An analogue of Cobham's theorem for graph directed iterated function systems

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}β$ , for integers $β$ . By using a result of Boigelot 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 $β$ . We introduce a logical formalism that permits to characterize sets of $\mathbb{R}^n$ whose representations in base $β$ are recognized by some Büchi automata. This result depends on the algebraic properties of the base: $β$ 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.

preprint2011arXiv

Enumeration and Decidable Properties of Automatic Sequences

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.

preprint2010arXiv

Multi-dimensional sets recognizable in all abstract numeration systems

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.

preprint2010arXiv

State Complexity of Testing Divisibility

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m >= 2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of the multiples of m in the Fibonacci system is exactly 2m^2.

preprint2010arXiv

The growth function of S-recognizable sets

A set $X\subseteq\mathbb N$ is S-recognizable for an abstract numeration system S if the set $\rep_S(X)$ of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set is always either $Θ((\log(n))^{c-df}n^f)$ where $c,d\in\mathbb N$ and $f\ge 1$ , or $Θ(n^r θ^{Θ(n^q)})$ , where $r,q\in\mathbb Q$ with $q\le 1$ . If the number of words of length n in the numeration language is bounded by a polynomial, then the growth function of an S-recognizable set is $Θ(n^r)$ , where $r\in \mathbb Q$ with $r\ge 1$ . Furthermore, for every $r\in \mathbb Q$ with $r\ge 1$ , we can provide an abstract numeration system S built on a polynomial language and an S-recognizable set such that the growth function of X is $Θ(n^r)$ . For all positive integers k and l, we can also provide an abstract numeration system S built on a exponential language and an S-recognizable set such that the growth function of X is $Θ((\log(n))^k n^l)$ .

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Emilie Charlier

Research overview

Is this your work?

8 publications

Asymptotic properties of free monoid morphisms

Abelian bordered factors and periodicity

On a group theoretic generalization of the Morse-Hedlund theorem

An analogue of Cobham's theorem for graph directed iterated function systems

Enumeration and Decidable Properties of Automatic Sequences

Multi-dimensional sets recognizable in all abstract numeration systems

State Complexity of Testing Divisibility

The growth function of S-recognizable sets

See the researcher in context

Building this map preview