References of "Vandomme, Elise"
     in
Bookmark and Share    
See detailSelected Topics in Combinatorics on Words
Brlek, Srecko; Dolce, Francesco; Reutemauer, Christophe et al

Book published by Elsevier (in press)

Detailed reference viewed: 22 (3 ULiège)
See detailNew notions of recurrence in a multidimensional setting
Vandomme, Elise ULiege

Scientific conference (2019, February)

In one dimension, an infinite word is said to be recurrent if every prefix occurs at least twice. A straightforward extension of this definition in higher dimensions turns out to be rather unsatisfying ... [more ▼]

In one dimension, an infinite word is said to be recurrent if every prefix occurs at least twice. A straightforward extension of this definition in higher dimensions turns out to be rather unsatisfying. In this talk, we present several notions of recurrence in the multidimensional case. In particular, we are interested in words having the property to be strongly uniformly recurrent: for each direction q, every prefix occurs in that direction (i.e. in positions iq) with bounded gaps. We will provide several constructions of such words and focus on the strongly uniform recurrence in the case of square morphisms. Joint work with Émilie Charlier and Svetlana Puzynina. [less ▲]

Detailed reference viewed: 11 (1 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)
See detailNew notions of recurrence in a multidimensional setting
Vandomme, Elise ULiege

Scientific conference (2018, November)

In one dimension, an infinite word is said to be recurrent if every prefix occurs at least twice. A straightforward extension of this definition in higher dimensions turns out to be rather unsatisfying ... [more ▼]

In one dimension, an infinite word is said to be recurrent if every prefix occurs at least twice. A straightforward extension of this definition in higher dimensions turns out to be rather unsatisfying. In this talk, we present several notions of recurrence in the multidimensional case. In particular, we are interested in words having the property to be strongly uniformly recurrent: for each direction q, every prefix occurs in that direction (i.e. in positions iq) with bounded gaps. We will provide several constructions of such words and focus on the strongly uniform recurrence in the case of square morphisms. Joint work with Émilie Charlier and Svetlana Puzynina. [less ▲]

Detailed reference viewed: 7 (0 ULiège)
See detailTwo algorithms to compute the maximal number of leaves in induced subtrees
Vandomme, Elise ULiege

Scientific conference (2018, October)

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we ... [more ▼]

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we require the subtrees to be induced and compute their maximal number of leaves. The problem, which is NP-complete in general, becomes polynomial in the case of trees. The leaf function associates to a number n the maximal number of leaves an induced subtree of size n can have. To compute the leaf function, we provide an efficient branch and bound algorithm. In the particular case of trees, we describe a polynomial algorithm using the dynamic programming paradigm. We conclude by exhibiting a link between the leaf functions of caterpillar graphs and a particular class of words called prefix normal. [less ▲]

Detailed reference viewed: 10 (0 ULiège)
See detailRecurrence dans les mots 2D
Vandomme, Elise ULiege

Scientific conference (2018, October)

En une dimension, un mot infini est récurrent si tout préfixe apparaît au moins deux fois dans ce mot. En particulier, cela signifie que tout facteur apparaît infiniment souvent. La généralisation ... [more ▼]

En une dimension, un mot infini est récurrent si tout préfixe apparaît au moins deux fois dans ce mot. En particulier, cela signifie que tout facteur apparaît infiniment souvent. La généralisation naturelle de cette notion aux mots infinis multidimensionnels se révèle rapidement insatisfaisante. Dans cet exposé, nous présentons plusieurs notions de récurrence des mots infinis deux-dimensionnels. En particulier, nous nous intéresserons aux mots ayant la propriété d'être fortement uniformément récurrent, c'est-à-dire que pour chaque pente $(p,q)$ avec $p$ et $q$ premiers entre eux, chaque préfixe apparaît dans cette direction, aux positions $i(p,q)$, à lacunes bornées. Nous donnerons plusieurs constructions de tels mots et étudierons la récurrence fortement uniforme des points fixes de morphismes carrés. [less ▲]

Detailed reference viewed: 7 (0 ULiège)
See detailÉté+kayak+laval=LoL. Qu'ont en commun les termes de cette équation?
Vandomme, Elise ULiege

Speech/Talk (2018)

Été + kayak + Laval = LoL … Qu’ont en commun tous les termes de cette équation? Ce sont des mots palindromes! On peut les lire dans les deux sens et on obtient le même mot. Stéphanie Schanck et Élise ... [more ▼]

Été + kayak + Laval = LoL … Qu’ont en commun tous les termes de cette équation? Ce sont des mots palindromes! On peut les lire dans les deux sens et on obtient le même mot. Stéphanie Schanck et Élise Vandomme nous présentent un résultat récent sur les nombres palindromes. En combinant un article de J. Cilleruelo, F. Luca & L. Baxter avec un article de A. Rajasekaran, J. Shallit & T. Smith, on obtient que tout entier est la somme de trois nombres palindromes, lorsque tous ces nombres sont écrits dans une certaine base. [less ▲]

Detailed reference viewed: 44 (6 ULiège)
See detailCritical exponents of balanced words
Vandomme, Elise ULiege

Scientific conference (2018, June)

Over a binary alphabet it is well-known that the aperiodic balanced words are exactly the Sturmian words. The repetitions in Sturmian words are well-understood. In particular, there is a formula for the ... [more ▼]

Over a binary alphabet it is well-known that the aperiodic balanced words are exactly the Sturmian words. The repetitions in Sturmian words are well-understood. In particular, there is a formula for the critical exponent (supremum of exponents e such that $x^e$ is a factor for some word x) of a Sturmian word. It is known that the Fibonacci word has the least critical exponent over all Sturmian words and this value is $(5+\sqrt{5})/2$. However, little is known about the critical exponents of balanced words over larger alphabets. We show that the least critical exponent among ternary balanced words is $2+\sqrt{2}/2$ and we construct a balanced word over a four-letter alphabet with critical exponent $(5+\sqrt{5})/4$. This is joint work with N. Rampersad and J. Shallit. [less ▲]

Detailed reference viewed: 7 (0 ULiège)
See detailCaterpillar graphs and their link with prefix normal words
Vandomme, Elise ULiege

Scientific conference (2018, June)

Étant donné un graphe G, nous nous intéressons au nombre L(i) qui est le nombre maximum de feuilles qu'un sous-arbre induit de taille i peut posséder. Dans ce contexte, nous introduisons le problème de ... [more ▼]

Étant donné un graphe G, nous nous intéressons au nombre L(i) qui est le nombre maximum de feuilles qu'un sous-arbre induit de taille i peut posséder. Dans ce contexte, nous introduisons le problème de "réalisation" qui consiste à determiner si, pour une suite donnée d'entiers (k_0,k_1,...,k_n), il existe un graphe G à n sommets tel que k_i = L(i) pour tout i entre 0 et n. Dans cet exposé, nous présentons une réponse partielle à ce problème en nous restreignant à l'ensemble des graphes chenilles. Les suites d'entiers qui sont réalisées par des graphes chenilles sont en lien avec une famille de mots binaires, connus sous le nom de mots préfixes normaux. Ces mots sont définis par le fait que leurs préfixes contiennent au moins autant de 1 que n'importe quel facteur de même longueur. [less ▲]

Detailed reference viewed: 8 (0 ULiège)
Full Text
Peer Reviewed
See detailFully leafed induced subtrees
Vandomme, Elise ULiege

Conference (2018, June)

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we ... [more ▼]

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we require the subtrees to be induced and compute their maximal number of leaves. The problem, which is NP-complete in general, becomes polynomial in the case of trees. The leaf function associates to a number n the maximal number of leaves an induced subtree of size n can have. To compute the leaf function, we provide an efficient branch and bound algorithm. In the particular case of trees, we provide a polynomial algorithm using the dynamic programming paradigm. [less ▲]

Detailed reference viewed: 19 (4 ULiège)
See detailCritical exponents of inifinite balanced words
Vandomme, Elise ULiege

Scientific conference (2018, May)

Over a binary alphabet it is well-known that the aperiodic balanced words are exactly the Sturmian words. The repetitions in Sturmian words are well-understood. In particular, there is a formula for the ... [more ▼]

Over a binary alphabet it is well-known that the aperiodic balanced words are exactly the Sturmian words. The repetitions in Sturmian words are well-understood. In particular, there is a formula for the critical exponent (supremum of exponents e such that $x^e$ is a factor for some word x) of a Sturmian word. It is known that the Fibonacci word has the least critical exponent over all Sturmian words and this value is $(5+\sqrt{5})/2$. However, little is known about the critical exponents of balanced words over larger alphabets. We show that the least critical exponent among ternary balanced words is $2+\sqrt{2}/2$ and we construct a balanced word over a four-letter alphabet with critical exponent $(5+\sqrt{5})/4$. This is joint work with N. Rampersad and J. Shallit. [less ▲]

Detailed reference viewed: 9 (0 ULiège)
Full Text
Peer Reviewed
See detailMaximal number of leaves in induced subtrees
Vandomme, Elise ULiege

Conference (2018, May)

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we ... [more ▼]

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we require the subtrees to be induced and compute their maximal number of leaves. The problem, which is NP-complete in general, becomes polynomial in the case of trees. The leaf function associates to a number n the maximal number of leaves an induced subtree of size n can have. To compute the leaf function, we provide an efficient branch and bound algorithm. In the particular case of trees, we describe a polynomial algorithm using the dynamic programming paradigm. [less ▲]

Detailed reference viewed: 20 (4 ULiège)
See detailFully leafed induced subtrees
Vandomme, Elise ULiege

Scientific conference (2018, April)

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we ... [more ▼]

Subtrees of graphs, as well as their number of leaves, have been investigated by various communities: from discrete mathematics to data mining and information retrieval. We consider a variant where we require the subtrees to be induced and compute their maximal number of leaves. The problem, which is NP-complete in general, becomes polynomial in the case of trees. The leaf function associates to a number n the maximal number of leaves an induced subtree of size n can have. To compute the leaf function, we provide an efficient branch and bound algorithm. In the particular case of trees, we describe a polynomial algorithm using the dynamic programming paradigm. We conclude by exhibiting a link between the leaf functions of caterpillar graphs and a particular class of words called prefix normal. [less ▲]

Detailed reference viewed: 9 (0 ULiège)
See detailLe Jeu de la Vie
Vandomme, Elise ULiege

Speech/Talk (2018)

Qu’est-ce qui caractérise la vie ? Son caractère auto-reproductif ? Élise Vandomme et Stéphanie Schanck nous présente un modèle artificiel qui simule la vie : le Jeu de la Vie.

Detailed reference viewed: 8 (0 ULiège)
See detailLa BlockChain, cette technologie qui se cache derrière le BitCoin
Vandomme, Elise ULiege

Speech/Talk (2018)

Les cryptomonnaies connaissent un engouement sans précédent. Introduites depuis moins de 10 ans, elles fonctionnent selon un protocole accessible par tous et décentralisé. Tout cela est possible grâce à ... [more ▼]

Les cryptomonnaies connaissent un engouement sans précédent. Introduites depuis moins de 10 ans, elles fonctionnent selon un protocole accessible par tous et décentralisé. Tout cela est possible grâce à la BlockChain, qui est une technologie prometteuse dont l’utilité dépasse le cadre des cryptomonnaies. Élise Vandomme et Stéphanie Schanck nous expliquent la structure de cette BlockChain. [less ▲]

Detailed reference viewed: 22 (0 ULiège)
See detailLes dessous du jeu de Set
Vandomme, Elise ULiege

Speech/Talk (2018)

La chronique Mathématiques de Nadia Lafrenière et Élise Vandomme du 12 février 2018 sur les mathématiques cachées derrière le jeu de cartes nommé Set. Elles nous parlent des dernières avancées ... [more ▼]

La chronique Mathématiques de Nadia Lafrenière et Élise Vandomme du 12 février 2018 sur les mathématiques cachées derrière le jeu de cartes nommé Set. Elles nous parlent des dernières avancées mathématiques au sujet du nombre de cartes nécessaires pour forcément avoir un set, peu importe les cartes choisies [less ▲]

Detailed reference viewed: 8 (0 ULiège)
Full Text
Peer Reviewed
See detailNearest constrained circular words
Blin, Guillaume; Blondin Massé, Alexandre; Gasparoux, Marie et al

in Leibniz International Proceedings in Informatics (2018), 105(6), 1-14

We study circular words arising in the development of equipment using shields in brachytherapy. This equipment has physical constraints that have to be taken into consideration. From an algorithmic point ... [more ▼]

We study circular words arising in the development of equipment using shields in brachytherapy. This equipment has physical constraints that have to be taken into consideration. From an algorithmic point of view, the problem can be formulated as follows: Given a circular word, find a constrained circular word of the same length such that the Manhattan distance be- tween these two words is minimal. We show that we can solve this problem in pseudo polynomial time (polynomial time in practice) using dynamic programming. [less ▲]

Detailed reference viewed: 15 (2 ULiège)
Full Text
Peer Reviewed
See detailFully leafed induced subtrees
Blondin Massé, Alexandre; De Carufel, Julien; Goupil, Alain et al

in Lecture Notes in Computer Science (2018), 10979

We consider the problem LIS of deciding whether there exists an induced subtree with exactly 𝑖≤𝑛 vertices and ℓ leaves in a given graph G with n vertices. We study the associated optimization problem ... [more ▼]

We consider the problem LIS of deciding whether there exists an induced subtree with exactly 𝑖≤𝑛 vertices and ℓ leaves in a given graph G with n vertices. We study the associated optimization problem, that consists in computing the maximal number of leaves, denoted by 𝐿𝐺(𝑖), realized by an induced subtree with i vertices, for 0≤𝑖≤𝑛. We begin by proving that the LIS problem is NP-complete in general. Then, we describe a nontrivial branch and bound algorithm that computes the function 𝐿𝐺 for any simple graph G. In the special case where G is a tree of maximum degree 𝛥, we provide a O(𝛥𝑛^3) time and O(𝑛^2) space algorithm to compute the function 𝐿𝐺. [less ▲]

Detailed reference viewed: 18 (3 ULiège)
Full Text
Peer Reviewed
See detailLeaf realization problem, caterpillar graphs and prefix normal words
Blondin Massé, Alexandre; De Carufel, Julien; Goupil, Alain et al

in Theoretical Computer Science (2018), 732

Given a simple graph G with n vertices and a natural number i<n+1, let be L(i) the maximum number of leaves that can be realized by an induced subtree T of G with i vertices. We introduce a problem that ... [more ▼]

Given a simple graph G with n vertices and a natural number i<n+1, let be L(i) the maximum number of leaves that can be realized by an induced subtree T of G with i vertices. We introduce a problem that we call the leaf realization problem, which consists in deciding whether, for a given sequence of n+1 natural numbers (l_0,l_1,...,l_n), there exists a simple graph G with n vertices such that L(i)=l_i for i=0,...,n . We present basic observations on the structure of these sequences for general graphs and trees. In the particular case where G is a caterpillar graph, we exhibit a bijection between the set of the discrete derivatives and the set of prefix normal words. [less ▲]

Detailed reference viewed: 23 (5 ULiège)
Full Text
Peer Reviewed
See detailCritical exponents of infinite balanced words
Rampersad, Narad; Shallit, Jeffrey; Vandomme, Elise ULiege

in Theoretical Computer Science (2018), In press

Over an alphabet of size 3 we construct an infinite balanced word with critical exponent 2+\sqr{2}/2 . Over an alphabet of size 4 we construct an infinite balanced word with critical exponent (5+\sqr{5 ... [more ▼]

Over an alphabet of size 3 we construct an infinite balanced word with critical exponent 2+\sqr{2}/2 . Over an alphabet of size 4 we construct an infinite balanced word with critical exponent (5+\sqr{5})/4. Over larger alphabets, we give some candidates for balanced words (found computationally) having small critical exponents. We also explore a method for proving these results using the automated theorem prover Walnut. [less ▲]

Detailed reference viewed: 15 (5 ULiège)