Feedback

Faculté des Sciences
Faculté des Sciences
MASTER THESIS
VIEW 174 | DOWNLOAD 512

Au sujet de la complexité k-binomiale

Download
Lejeune, Marie ULiège
Promotor(s) : Rigo, Michel ULiège
Date of defense : 27-Jun-2018 • Permalink : http://hdl.handle.net/2268.2/5007
Details
Title : Au sujet de la complexité k-binomiale
Author : Lejeune, Marie ULiège
Date of defense  : 27-Jun-2018
Advisor(s) : Rigo, Michel ULiège
Committee's member(s) : Mathonet, Pierre ULiège
Charlier, Emilie ULiège
Leroy, Julien ULiège
Language : French
Number of pages : 100
Keywords : [fr] combinatoire
[fr] mots
[fr] complexité
[fr] coefficient binomial
[en] combinatorics
[en] words
[en] complexity
[en] binomial coefficient
Discipline(s) : Physical, chemical, mathematical & earth Sciences > Mathematics
Target public : Researchers
Professionals of domain
Student
Institution(s) : Université de Liège, Liège, Belgique
Degree: Master en sciences mathématiques, à finalité spécialisée en informatique
Faculty: Master thesis of the Faculté des Sciences

Abstract

[fr] Les principaux objectifs de ce travail sont de présenter les notions d’équivalence et de complexité k-binomiales, ainsi qu’étudier quelques problèmes qui y sont directement liés.

Rappelons tout d’abord que deux mots finis u et v sur un alphabet A sont k-binomialement équivalents si, pour tout mot w de longueur au plus k, le coefficient binomial de u et w (comptant le nombre d’occurrences de w comme sous-mot de u) est égal au coefficient binomial de v et w.

Après avoir introduit la notion d’équivalence k-binomiale et avoir donné une borne asymptotique sur le nombre maximal de classes d’équivalence parmi les facteurs de longueur n d’un mot donné, nous présentons la notion de complexité k-binomiale d’un mot infini. Il s’agit d’une application associant à chaque naturel n le nombre de facteurs de longueur n dans le mot x, à équivalence k-binomiale près. Ensuite, nous étudions cette complexité sur les mots sturmiens qui sont les mots apériodiques de complexité factorielle minimale. Nous montrons une définition équivalente des mots sturmiens : il s’agit de l’ensemble des mots infinis apériodiques et équilibrés. Utilisant cette seconde définition, nous pouvons montrer que les mots sturmiens ont une complexité k-binomiale égale à leur
complexité factorielle : p(n)=n+1, pout tout k>1.

Dans ce travail sont également étudiés les mots infinis points fixes de morphismes Parikh-constants, c’est-à-dire de morphismes pour lesquels les images de chaque lettre sont égales à permutation près. Il est possible de montrer que la complexité k-binomiale de tels mots est bornée, pour tout naturel k. Nous essayons ensuite de calculer la complexité k-binomiale du mot de Thue-Morse. Ce travail n’a pas été mené auparavant et nous essayons, conjointement avec Michel Rigo et Julien Leroy, de prouver la conjecture
affirmant que le nombre de facteurs de longueur n, à équivalence k-binomiale près, vaut 3.2^k-3 ou 3.2^k-4, en fonction de la valeur de n modulo 2^k.

Le chapitre suivant étudie la cardinalité minimale d’un alphabet permettant de construire un mot infini ne comportant pas de carré 2-binomial, c’est-à-dire de mot de la forme u.v où u et v sont 2-binomialement équivalents. Nous effectuons ensuite le même travail pour trouver un mot évitant les cubes 2-binomiaux.

Enfin, le dernier chapitre propose un algorithme polynomial testant si deux mots finis sont k-binomialement équivalents ou non. Cet algorithme associe à chaque mot u un automate à multiplicités qui accepte exactement les sous-mots de u. Il est ensuite possible de vérifier en temps polynomial si deux automates sont équivalents.

[en] The main goals of this work are to present the notions of k-binomial equivalence, k-binomial complexity and to study some problems directly connected.

Let us recall that two finite words u and v over an alphabet A are k-binomially equivalent if, for all words w of length up to k, the binomial coefficient of u and w – counting the number of occurrences of w as a subword of u – equals the binomial coefficient of v and w.

After having introduced k-binomial equivalence and having established an asymptotic bound on the maximal number of k-binomial classes among factors of length n of an infinite word x, I present the notion of k-binomial complexity of an infinite word x which is a map that associates with each positive integer n the number of factors of length n in the word x, up to k-binomial equivalence. Then I study this complexity on Sturmian words which are aperiodic words with the least factor complexity. I show in this master thesis an equivalent definition for Sturmian words: these words are the set of aperiodic and balanced infinite words. Using that alternative definition, I am able to show that k-binomial complexity of Sturmian words equals their factor complexity p(n)=n+1, for all k>1.

In this master thesis, I am also interested in infinite words that are fixed points of a Parikh-constant morphism, that is, a morphism for which images of all letters are equal, up to permutation. It is possible to show that for such words, their k-binomial complexity is bounded for every k>0. After that general fact, I try to compute the complexity for the Thue-Morse word t=0110100110010110…. That work has never been carried on before and, working in collaboration with Michel Rigo and Julien Leroy, we are trying to solve the conjecture stating that, for every k>1, the number of factors of length n in t, up to k-binomial equivalence, equals 3.2^k-3 or 3.2^k-4, depending on the value of n modulo 2^k.

The next chapter of my master thesis presents the minimal cardinality of an alphabet allowing the explicit construction of an infinite word avoiding 2-binomial squares, that is, factors of the form u.v such that u and v are 2-binomially equivalent. Then I carry on the same work trying this time to avoid 2-binomial cubes.

Finally, the last chapter gives a polynomial-time algorithm testing if two finite words are k-binomially equivalent or not. This algorithm builds, for every word u, an automaton with multiplicities for which accepting paths are exactly labelled by subwords of u. The remaining problem is to decide if two automata with multiplicities are equivalent. I show that this problem is solvable in polynomial-time.


File(s)

Document(s)

File
Access Memoire_Marie_Lejeune.pdf
Description:
Size: 836.21 kB
Format: Adobe PDF

Author

  • Lejeune, Marie ULiège Université de Liège > Master sc. math., à fin.

Promotor(s)

Committee's member(s)

  • Total number of views 174
  • Total number of downloads 512










All documents available on MatheO are protected by copyright and subject to the usual rules for fair use.
The University of Liège does not guarantee the scientific quality of these students' works or the accuracy of all the information they contain.