To see the other types of publications on this topic, follow the link: Combinatorics on words.
Dissertations / Theses on the topic 'Combinatorics on words'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 46 dissertations / theses for your research on the topic 'Combinatorics on words.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Ochem, Pascal. "Graph coloring and combinatorics on words." Bordeaux 1, 2005. http://www.theses.fr/2005BOR13083.
Full textAbstract:
Dans une première partie, nous nous intéressons à différentes colorations de graphes peu denses, en particulier des sous-classes des graphes planaires. Nous apportons de nouveaux résultats concernant les colorations impropres acycliques et la coloration orientée. Nous définissons également de nouvelles colorations d'arètes, les arboricités T-libres, qui généralisent notamment l'arboricité étoile et l'arboricité chenille. Dans une seconde partie, nous considérons certains problèmes de combinatoire des mots. Nous présentons des avancées algorithmiques nous permettant d'étudier assez finement une généralisation du seuil de répétition. Nous obtenons aussi des preuves de 2-évitabilité pour certains motifs. Enfin, nous améliorons des bornes sur la fréquence minimale ou maximale d'une lettre dans un mot infini évitant certaines répétitions.
2
Wang, Ming-wei. "Periodicity and Repetition in Combinatorics on Words." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1136.
Full textAbstract:
This thesis concerns combinatorics on words. I present many results in this area, united by the common themes of periodicity and repetition. Most of these results have already appeared in journal or conference articles. Chapter 2 – Chapter 5 contain the most significant contribution of this thesis in the area of combinatorics on words. Below we give a brief synopsis of each chapter. Chapter 1 introduces the subject area in general and some background information. Chapter 2 and Chapter 3 grew out of attempts to prove the Decreasing Length Conjecture (DLC). The DLC states that if ′ is a morphism over an alphabet of size n then for any word w, there exists 0 ≤ i < j ≤ n such that |′i(w)| ≤ |′j(w)|. The DLC was proved by S. Cautis and S. Yazdani in Periodicity, morphisms, and matrices in Theoret. Comput. Sci. (295) 2003, 107-121. More specifically, Chapter 2 gives two generalizations of the classical Fine and Wilf theorem which states that if (fn)n≥0, (gn)n≥0 are two periodic sequences of real numbers, of period lengths h and k respectively, (a) If fn = gn for 0 ≤ n < h + k - gcd(h;k), then fn = gn for all n ≥ 0.
(b) The conclusion in (a) would be false if h + k - gcd(h;k) were replaced by any smaller number. We give similar results where equality in (a) is replaced by inequality and to more than two sequences. These generalizations can be used to prove weak versions of the DLC. Chapter 3 gives an essentially optimal bound to the following matrix problem. Let A be an n × n matrix with non-negative integer entries. Let f(n) be the smallest integer such that for all A, there exist i < j ≤ f(n) such that Ai ≤ Aj, where A ≤ B means each entry of A is less than or equal to the corresponding entry in B. The question is to find good upper bounds on f(n). This problem has been attacked in two different ways. We give a method that proves an essentially optimal upper bound of n + g(n) where g(n) is the maximum order of an element of the symmetric group on n objects. A second approach yields a slightly worse upper bound. But this approach has a result of independent interest concerning irreducible matrices. A non-negative n × n matrix A is irreducible if ∑{i=0}^{n-1}Ai has all entries strictly positive. We show in Chapter 3 that if A is an irreducible n × n matrix, then there exists an integer e > 0 with e = O(n log n) such that the diagonal entries of Ae are all strictly positive. These results improve on results in my Master's thesis and is a version of the DLC in the matrix setting. They have direct applications to the growth rate of words in a D0L system. Chapter 4 gives a complete characterization of two-sided fixed points of morphisms. A weak version of the DLC is used to prove a non-trivial case of the characterization. This characterization completes the previous work of Head and Lando on finite and one-sided fixed points of morphisms. Chapter 5, 6 and 7 deal with avoiding different kinds of repetitions in infinite words. Chapter 5 deals with problems about simultaneously avoiding cubes and large squares in infinite binary words. We use morphisms and fixed points to construct an infinite binary word that simultaneously avoid cubes and squares xx with |x| ≥ 4. M. Dekking was the first to show such words exist. His construction used a non-uniform morphism. We use only uniform morphisms in Chapter 5. The construction in Chapter 5 is somewhat simpler than Dekking's. Chapter 6 deals with problems of simultaneously avoiding several patterns at once. The patterns are generated by a simple arithmetic operation. Chapter 7 proves a variant of a result of H. Friedman. We say a word y is a subsequence of a word z if y can be obtained by striking out zero or more symbols from z. Friedman proved that over any finite alphabet, there exists a longest finite word x = x₁x₂ ··· xn such that xixii+1 ··· x₂i is not a subsequence of xjxj+1 ··· x₂j for 1 ≤ i < j ≤ n/2. We call such words self-avoiding. We show that if “subsequence” is replaced by “subword” in defining self-avoiding, then there are infinite self-avoiding words over a 3-letter alphabet but not over binary or unary alphabets. This solves a question posed by Jean-Paul Allouche. In Chapter 8 we give an application of the existence of infinitely many square-free words over a 3-letter alphabet. The duplication language generated by a word w is roughly speaking the set of words that can be obtained from w by repeatedly doubling the subwords of w. We use the existence of infinitely many square-free words over a 3-letter alphabet to prove that the duplication language generated by a word containing at least 3 distinct letters is not regular. This solves an open problem due to J. Dassow, V. Mitrana and Gh. Paun. It is known that the duplication language generated by a word over a binary alphabet is regular. It is not known whether such languages are context-free if the generator word contains at least 3 distinct letters. After the defence of my thesis I noticed that essentially the same argument was given by Ehrenfeucht and Rozenberg in Regularity of languages generated by copying systems in Discrete Appl. Math. (8) 1984, 313-317. Chapter 9 defines a new “descriptive” measure of complexity of a word w by the minimal size of a deterministic finite automaton that accepts w (and possibly other words) but no other words of length |w|. Lower and upper bounds for various classes of words are proved in Chapter 9. Many of the proofs make essential use of repetitions in words.
3
Klouda, karel. "Non-standard numeration systemes and combinatorics on words." Paris 7, 2010. http://www.theses.fr/2010PA077161.
Full textAbstract:
La thèse est divisée en 7 chapitres. Le premier chapitre est introductif, et contient des informations basiques sur la bêta-numération, la combinatoire des mots, les nombres p-adiques et la théorie des automates. Dans le chapitre 2 nous proposons une nouvelle méthode pour trouver tous les facteurs bispéciaux du point fixe d'une substitution circulaire. Cette méthode est appliquée dans le chapitre 3 sur les mots infinis associés à des nombres de Parry non simples. En utilisant la connaissance de la structure des facteurs bispéciaux, la complexité en terme des facteurs et l'exposant critique de ces mots est calculée dans les chapitres 4 et 5 respectivement. Le chapitre 6 concerne la complexité en terme des facteurs et la complexité palindromique des mots qui apparaissent comme bêta-développements du nombre 1 quand bêta est univoque. Dans le dernier chapitre, chapitre 7, nous étudions quatre systèmes de numération à base rationnelleThe thesis is divided into 7 chapters. Chapter 1 is introductory, containing basic facts on beta numeration, combinatorics on words, and p-adic and automata theory. In Chapter 2, a new method of how to find all bispecial factors in a fixed point of a circular substitution is proposed. This method is applied in Chapter 3 on the infinite words associated with non-simple Parry numbers. Using the Knowledge of the structure of bispecial factors, the factors complexity and the critical exponent of these words is computed in Chapters 4 and 5, respectively. Chapter 6 is concerned with the factor and palindromic complexity of words which arise as the beta-expansions of the number 1 with beta being a univoque number. In the last Chapter 7, four different rational base numeration Systems for p-adic numbers are studied
4
Cassels, Joshua, and Anant Godbole. "Covering Arrays for Equivalence Classes of Words." Digital Commons @ East Tennessee State University, 2018. https://dc.etsu.edu/honors/446.
Full textAbstract:
Covering arrays for words of length t over a d letter alphabet are k × n arrays with entries from the alphabet so that for each choice of t columns, each of the dt t-letter words appears at least once among the rows of the selected columns. We study two schemes in which all words are not considered to be different. In the first case, words are equivalent if they induce the same partition of a t element set. In the second case, words of the same weighted sum are equivalent. In both cases we produce logarithmic upper bounds on the minimum size k = k(n) of a covering array. Most definitive results are for t = 2, 3, 4.
5
Rampersad, Narad. "Infinite Sequences and Pattern Avoidance." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1155.
Full textAbstract:
The study of combinatorics on words dates back at least to the beginning of the 20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains no squares (identical adjacent blocks) xx. This result was eventually used to solve some longstanding open problems in algebra and has remarkable connections to other areas of mathematics and computer science as well. In this thesis we primarily study several variations of the problems studied by Thue in his work on repetitions in words, including some recent connections to other areas, such as graph theory. In Chapter 1 we give a brief introduction to the subject of combinatorics on words. In Chapter 2 we use uniform morphisms to construct an infinite binary word that contains no cubes xxx and no squares yy with |y| ≥ 4, thus giving a simpler construction than that of Dekking. We also use uniform morphisms to construct an infinite binary word avoiding all squares except 0², 1², and (01)², thus giving a simpler construction than that of Fraenkel and Simpson. We give some new enumeration results for these avoidance properties and solve an open problem of Prodinger and Urbanek regarding the perfect shuffle of infinite binary words that avoid arbitrarily large squares. In Chapter 3 we examine ternary squarefree words in more detail, and in Chapter 4 we study words w satisfying the property that for any sufficiently long subword w' of w, w does not contain the reversal of w' as a subword. In Chapter 5 we discuss an application of the property of squarefreeness to colourings of graphs. In Chapter 6 we study strictly increasing sequences (a(n))n≥0 of non-negative integers satisfying the equation a(a(n)) = dn. Finally, in Chapter 7 we give a brief conclusion and present some open problems.
6
Vandomme, Elise. "Contributions to combinatorics on words in an abelian context and covering problems in graphs." Thesis, Université Grenoble Alpes (ComUE), 2015. http://www.theses.fr/2015GRENM010/document.
Full textAbstract:
Cette dissertation se divise en deux parties, distinctes mais connexes, qui sont le reflet de la cotutelle. Nous étudions et résolvons des problèmes concernant d'une part la combinatoire des mots dans un contexte abélien et d'autre part des problèmes de couverture dans des graphes. Chaque question fait l'objet d'un chapitre. En combinatoire des mots, le premier problème considéré s'intéresse à la régularité des suites au sens défini par Allouche et Shallit. Nous montrons qu'une suite qui satisfait une certaine propriété de symétrie est 2-régulière. Ensuite, nous appliquons ce théorème pour montrer que les fonctions de complexité 2-abélienne du mot de Thue--Morse ainsi que du mot appelé ''period-doubling'' sont 2-régulières. Les calculs et arguments développés dans ces démonstrations s'inscrivent dans un schéma plus général que nous espérons pouvoir utiliser à nouveau pour prouver d'autres résultats de régularité. Le deuxième problème poursuit le développement de la notion de mot de retour abélien introduite par Puzynina et Zamboni. Nous obtenons une caractérisation des mots sturmiens avec un intercepte non nul en termes du cardinal (fini ou non) de l'ensemble des mots de retour abélien par rapport à tous les préfixes. Nous décrivons cet ensemble pour Fibonacci ainsi que pour Thue--Morse (bien que cela ne soit pas un mot sturmien). Nous étudions la relation existante entre la complexité abélienne et le cardinal de cet ensemble. En théorie des graphes, le premier problème considéré traite des codes identifiants dans les graphes. Ces codes ont été introduits par Karpovsky, Chakrabarty et Levitin pour modéliser un problème de détection de défaillance dans des réseaux multiprocesseurs. Le rapport entre la taille optimale d'un code identifiant et la taille optimale du relâchement fractionnaire d'un code identifiant est comprise entre 1 et 2 ln(|V|)+1 où V est l'ensemble des sommets du graphe. Nous nous concentrons sur les graphes sommet-transitifs, car nous pouvons y calculer précisément la solution fractionnaire. Nous exhibons des familles infinies, appelées quadrangles généralisés, de graphes sommet-transitifs pour lesquelles les solutions entière et fractionnaire sont de l'ordre |V|^k avec k dans {1/4, 1/3, 2/5}. Le second problème concerne les (r,a,b)-codes couvrants de la grille infinie déjà étudiés par Axenovich et Puzynina. Nous introduisons la notion de 2-coloriages constants de graphes pondérés et nous les étudions dans le cas de quatre cycles pondérés particuliers. Nous présentons une méthode permettant de lier ces 2-coloriages aux codes couvrants. Enfin, nous déterminons les valeurs exactes des constantes a et b de tout (r,a,b)-code couvrant de la grille infinie avec |a-b|>4. Il s'agit d'une extension d'un théorème d'AxenovichThis dissertation is divided into two (distinct but connected) parts that reflect the joint PhD. We study and we solve several questions regarding on the one hand combinatorics on words in an abelian context and on the other hand covering problems in graphs. Each particular problem is the topic of a chapter. In combinatorics on words, the first problem considered focuses on the 2-regularity of sequences in the sense of Allouche and Shallit. We prove that a sequence satisfying a certain symmetry property is 2-regular. Then we apply this theorem to show that the 2-abelian complexity functions of the Thue--Morse word and the period-doubling word are 2-regular. The computation and arguments leading to these results fit into a quite general scheme that we hope can be used again to prove additional regularity results. The second question concerns the notion of return words up to abelian equivalence, introduced by Puzynina and Zamboni. We obtain a characterization of Sturmian words with non-zero intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the Thue-Morse word (which is not Sturmian). We investigate the relationship existing between the abelian complexity and the finiteness of this set. In graph theory, the first problem considered deals with identifying codes in graphs. These codes were introduced by Karpovsky, Chakrabarty and Levitin to model fault-diagnosis in multiprocessor systems. The ratio between the optimal size of an identifying code and the optimal size of a fractional relaxation of an identifying code is between 1 and 2 ln(|V|)+1 where V is the vertex set of the graph. We focus on vertex-transitive graphs, since we can compute the exact fractional solution for them. We exhibit infinite families, called generalized quadrangles, of vertex-transitive graphs with integer and fractional identifying codes of order |V|^k with k in {1/4,1/3,2/5}. The second problem concerns (r,a,b)-covering codes of the infinite grid already studied by Axenovich and Puzynina. We introduce the notion of constant 2-labellings of weighted graphs and study them in four particular weighted cycles. We present a method to link these labellings with covering codes. Finally, we determine the precise values of the constants a and b of any (r,a,b)-covering code of the infinite grid with |a-b|>4. This is an extension of a theorem of Axenovich
7
Rosenfeld, Matthieu. "Avoidability of Abelian Repetitions in Words." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEN033/document.
Full textAbstract:
Dans ce document, nous étudions l’évitabilité de différentes formes de répétitions dans les mots. En particulier 3 des 6 chapitres sont dédiés aux répétitions abéliennes en lien notamment avec deux questions d’Erdős de 1957 et 1961. Nous commençons par montrer qu’il existe un algorithme décidant, sous certaines conditions, si un mot morphique évite des puissances abéliennes. Cet algorithme élargit la classe sur laquelle les précédents algorithmes pouvaient décider. Une généralisation de cet algorithme nous permet de montrer que les longs carrés abéliens sont évitables sur l’alphabet ternaire et que les carrés additifs sont évitables sur Z2 . Le premier résultat répond à une question ouverte de Mäkelä datant de 2003 alors que le deuxième rappelle la question ouverte de 1994 concernant l’évitabilité des carrés additifs sur Z.Une autre généralisation de notre algorithme permet d’étudier l’évitabilité des motifs au sens abélien. Nous montrons que les motifs binaires de longueur supérieure à 14 sont évitables sur l’alphabet binaire, améliorant la précédente borne de 118.Nous donnons des conditions suffisantes pour qu’un morphisme soit sans longues puissances nème k-abéliennes. Ce résultat nous permet de calculer, pour tout k ≥ 3, le nombre minimum de carrés k-abéliens qu’un mot binaire infini doit contenir en facteur. Il permet aussi de montrer que les longs carrés 2-abéliens sont évitables sur l’alphabet binaire et qu’il existe un mot ternaire qui ne contient qu’un seul carré 2-abélien en tant que facteur.Enfin, nous proposons une classification complète des formules binaires en fonction de la taille d’alphabet qu’il faut pour les éviter et du taux de croissance (exponentiel ou polynomial) du langage les évitantIn this document, we study the avoidability of different kind of repetitions in words. We firstshow that under some conditions one can decide whether a morphic word avoids abelian n-thpowers. This algorithm can decide over a wider class of morphism than the previousalgorithms. We generalize this algorithm and use it to show that long abelian squares areavoidable over the ternary alphabet and that additive squares are avoidable over Z2 . The firstresult answers a weak version of a question formulated by Mäkelä in 2003 and the second oneis related to an open question from 1994 about the avoidability of additive squares over Z.Another generalization of this algorithm can be used to study avoidability of patterns in theabelian sense. In particular, we show that binary patterns of length more than 14 areavoidable over the binary alphabet in the abelian sense. This improves considerably theprevious bound of 118.We give sufficient conditions for a morphism to be long k-abelian n-th power-free. This resultallows us to compute for every k ≥ 3 the number of different k-abelian squares that a binaryword must contain. We prove that long 2-abelian squares are avoidable over the binaryalphabet and that over the ternary alphabet there exists a word that contains only one 2-abelian square.We also give a complete classification of binary formulas based on the size of the smallestalphabet over which they are avoidable and on the growth (exponential or polynomial) of theassociated language
8
Kristina, Ago Balog. "On some reversal-invariant complexity measures of multiary words." Phd thesis, Univerzitet u Novom Sadu, Prirodno-matematički fakultet u Novom Sadu, 2020. https://www.cris.uns.ac.rs/record.jsf?recordId=114649&source=NDLTD&language=en.
Full textAbstract:
We focus on two complexity measures of words that are invariant under the operation of reversal of a word: the palindromic defect and the MP-ratio.The palindromic defect of a given word w is dened by jwj + 1 jPal(w)j, where jPal(w)j denotes the number of palindromic factors of w. We study innite words, to which this de nition can be naturally extended. There are many results in the literature about the so- called rich words (words of defect 0), while words of nite positive defect have been studied signicantly less; for some time (until recently) it was not known whether there even exist such words that additionally are aperiodic and have their set of factors closed under reversal. Among the rst examples that appeared were the so-called highly potential words. In this thesis we present a much more general construction,which gives a wider class of words, named generalized highly potential words, and analyze their signicance within the frames of combinatorics on words.The MP-ratio of a given n-ary word w is dened as the quotient jrwsj jwj ,where r and s are words such that the word rws is minimal- palindromic and that the length jrj + jsj is minimal possible; here, an n-ary word is called minimal-palindromic if it does not contain palindromic subwords of length greater than jwj n . In the binary case, it was proved that the MP-ratio is well-dened and that it is bounded from above by 4, which is the best possible upper bound. The question of well- denedness of the MP-ratio for larger alphabets was left open. In this thesis we solve that question in the ternary case: we show that the MP-ratio is indeed well-dened in the ternary case, that it is bounded from above by the constant 6 and that this is the best possible upper bound.Izucavamo dve mere slozenosti reci koje su invarijantne u odnosu na operaciju preokretanja reci: palindromski defekt i MP-razmeru date reci.Palindromski defekt reci w denise se kao jwj + 1 jPal(w)j, gde jPal(w)j predstavlja broj palindromskih faktora reci w. Mi izucavamo beskonacne reci, na koje se ova denicija moze prirodno prosiriti. Postoje mnogobrojni rezultati u vezi sa tzv. bogatim recima (reci cije je defekt 0), dok se o recima sa konacnim pozitivnim defektom relativno malo zna; tokom jednog perioda (donedavno) nije bilo poznato ni da li uopste postoje takve reci koje su,dodatno, aperiodi cne i imaju skup faktora zatvoren za preokretanje. Medu prvim primerima koji su se pojavili u literaturi su bile tzv. visokopotencijalne reci. U disertaciji cemo predstaviti znatno opstiju konstrukciju, kojom se dobija znacajno sira klasa reci, nazvanih uop stene visokopotencijalne reci, i analiziracemo njihov znacaj u okvirima kombinatorike na recima.MP-razmera date n-arne reci w denise se kao kolicnik jrwsj jwj , gde su r i s takve da je rec rws minimalno-palindromicna, i duzina jrj + jsj je najmanja moguca; ovde, za n-arnu rec kazemo da je minimalno-palindromicna ako ne sadrzi palindromsku podrec duzine vece od jwj n . U binarnom slucaju dokazano je da je MP-razmera dobro denisana i da je ogranicena odozgo konstantom 4, sto je i najbolja moguca granica. Dobra denisanost MP-razmere za vece alfabete je ostavljena kao otvoren problem. U ovoj tezi resavamo taj problem u ternarnom slucaju: pokazacemo da MP- razmera jeste dobro de-nisana u ternarnom slucaju, da je ogranicena odozgo sa 6, i da se ta granica ne moze poboljsati.
9
Nevisi, Hossein. "Conditions on the existence of unambiguous morphisms." Thesis, Loughborough University, 2012. https://dspace.lboro.ac.uk/2134/10282.
Full textAbstract:
A morphism $\sigma$ is \emph{(strongly) unambiguous} with respect to a word $\alpha$ if there is no other morphism $\tau$ that maps $\alpha$ to the same image as $\sigma$. Moreover, $\sigma$ is said to be \emph{weakly unambiguous} with respect to a word $\alpha$ if $\sigma$ is the only \emph{nonerasing} morphism that can map $\alpha$ to $\sigma(\alpha)$, i.\,e., there does not exist any other nonerasing morphism $\tau$ satisfying $\tau(\alpha) = \sigma(\alpha)$. In the first main part of the present thesis, we wish to characterise those words with respect to which there exists a weakly unambiguous \emph{length-increasing} morphism that maps a word to an image that is strictly longer than the word. Our main result is a compact characterisation that holds for all morphisms with ternary or larger target alphabets. We also comprehensively describe those words that have a weakly unambiguous length-increasing morphism with a unary target alphabet, but we have to leave the problem open for binary alphabets, where we can merely give some non-characteristic conditions. \par The second main part of the present thesis studies the question of whether, for any given word, there exists a strongly unambiguous \emph{1-uniform} morphism, i.\,e., a morphism that maps every letter in the word to an image of length $1$. This problem shows some connections to previous research on \emph{fixed points} of nontrivial morphisms, i.\,e., those words $\alpha$ for which there is a morphism $\phi$ satisfying $\phi(\alpha) = \alpha$ and, for a symbol $x$ in $\alpha$, $\phi(x) \neq x$. Therefore, we can expand our examination of the existence of unambiguous morphisms to a discussion of the question of whether we can reduce the number of different symbols in a word that is not a fixed point such that the resulting word is again not a fixed point. This problem is quite similar to the setting of Billaud's Conjecture, the correctness of which we prove for a special case.
10
Uscka-Wehlou, Hanna. "Digital lines, Sturmian words, and continued fractions." Doctoral thesis, Uppsala : Matematiska institutionen, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-107274.
Full text
11
Rotondo, Pablo. "Probabilistic studies in number theory and word combinatorics : instances of dynamical analysis." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC213/document.
Full textAbstract:
L'analyse dynamique intègre des outils propres aux systèmes dynamiques (comme l'opérateur de transfert) au cadre de la combinatoire analytique, et permet ainsi l'analyse d'un grand nombre d'algorithmes et objets qu'on peut associer naturellement à un système dynamique. Dans ce manuscrit de thèse, nous présentons, dans la perspective de l'analyse dynamique, l'étude probabiliste de plusieurs problèmes qui semblent à priori bien différents : l'analyse probabiliste de la fonction de récurrence des mots de Sturm, et l'étude probabiliste de l'algorithme du “logarithme continu”. Les mots de Sturm constituent une famille omniprésente en combinatoire des mots. Ce sont, dans un sens précis, les mots les plus simples qui ne sont pas ultimement périodiques. Les mots de Sturm ont déjà été beaucoup étudiés, notamment par Morse et Hedlund (1940) qui en ont exhibé une caractérisation fondamentale comme des codages discrets de droites à pente irrationnelle. Ce résultat relie ainsi les mots de Sturm au système dynamique d'Euclide. Les mots de Sturm n'avaient jamais été étudiés d'un point de vue probabiliste. Ici nous introduisons deux modèles probabilistes naturels (et bien complémentaires) et y analysons le comportement probabiliste (et asymptotique) de la “fonction de récurrence” ; nous quantifions sa valeur moyenne et décrivons sa distribution sous chacun de ces deux modèles : l'un est naturel du point de vue algorithmique (mais original du point de vue de l'analyse dynamique), et l'autre permet naturellement de quantifier des classes de plus mauvais cas. Nous discutons la relation entre ces deux modèles et leurs méthodes respectives, en exhibant un lien potentiel qui utilise la transformée de Mellin. Nous avons aussi considéré (et c'est un travail en cours qui vise à unifier les approches) les mots associés à deux familles particulières de pentes : les pentes irrationnelles quadratiques, et les pentes rationnelles (qui donnent lieu aux mots de Christoffel). L'algorithme du logarithme continu est introduit par Gosper dans Hakmem (1978) comme une mutation de l'algorithme classique des fractions continues. Il calcule le plus grand commun diviseur de deux nombres naturels en utilisant uniquement des shifts binaires et des soustractions. Le pire des cas a été étudié récemment par Shallit (2016), qui a donné des bornes précises pour le nombre d'étapes et a exhibé une famille d'entrées sur laquelle l'algorithme atteint cette borne. Dans cette thèse, nous étudions le nombre moyen d'étapes, tout comme d'autres paramètres importants de l'algorithme. Grâce à des méthodes d'analyse dynamique, nous exhibons des constantes mathématiques précises. Le système dynamique ressemble à première vue à celui d'Euclide, et a été étudié d'abord par Chan (2005) avec des méthodes ergodiques. Cependant, la présence des puissances de 2 dans les quotients change la nature de l'algorithme et donne une nature dyadique aux principaux paramètres de l'algorithme, qui ne peuvent donc pas être simplement caractérisés dans le monde réel.C'est pourquoi nous introduisons un nouveau système dynamique, avec une nouvelle composante dyadique, et travaillons dans ce système à deux composantes, l'une réelle, et l'autre dyadique. Grâce à ce nouveau système mixte, nous obtenons l'analyse en moyenne de l'algorithmeDynamical Analysis incorporates tools from dynamical systems, namely theTransfer Operator, into the framework of Analytic Combinatorics, permitting the analysis of numerous algorithms and objects naturally associated with an underlying dynamical system.This dissertation presents, in the integrated framework of Dynamical Analysis, the probabilistic analysis of seemingly distinct problems in a unified way: the probabilistic study of the recurrence function of Sturmian words, and the probabilistic study of the Continued Logarithm algorithm.Sturmian words are a fundamental family of words in Word Combinatorics. They are in a precise sense the simplest infinite words that are not eventually periodic. Sturmian words have been well studied over the years, notably by Morse and Hedlund (1940) who demonstrated that they present a notable number theoretical characterization as discrete codings of lines with irrationalslope, relating them naturally to dynamical systems, in particular the Euclidean dynamical system. These words have never been studied from a probabilistic perspective. Here, we quantify the recurrence properties of a ``random'' Sturmian word, which are dictated by the so-called ``recurrence function''; we perform a complete asymptotic probabilistic study of this function, quantifying its mean and describing its distribution under two different probabilistic models, which present different virtues: one is a naturaly choice from an algorithmic point of view (but is innovative from the point of view of dynamical analysis), while the other allows a natural quantification of the worst-case growth of the recurrence function. We discuss the relation between these two distinct models and their respective techniques, explaining also how the two seemingly different techniques employed could be linked through the use of the Mellin transform. In this dissertation we also discuss our ongoing work regarding two special families of Sturmian words: those associated with a quadratic irrational slope, and those with a rational slope (not properly Sturmian). Our work seems to show the possibility of a unified study.The Continued Logarithm Algorithm, introduced by Gosper in Hakmem (1978) as a mutation of classical continued fractions, computes the greatest common divisor of two natural numbers by performing division-like steps involving only binary shifts and substractions. Its worst-case performance was studied recently by Shallit (2016), who showed a precise upper-bound for the number of steps and gave a family of inputs attaining this bound. In this dissertation we employ dynamical analysis to study the average running time of the algorithm, giving precise mathematical constants for the asymptotics, as well as other parameters of interest. The underlying dynamical system is akin to the Euclidean one, and was first studied by Chan (around 2005) from an ergodic, but the presence of powers of 2 in the quotients ingrains into the central parameters a dyadic flavour that cannot be grasped solely by studying this system. We thus introduce a dyadic component and deal with a two-component system. With this new mixed system at hand, we then provide a complete average-case analysis of the algorithm by Dynamical Analysis
12
Dolce, Francesco. "Codes bifixes, combinatoire des mots et systèmes dynamiques symboliques." Thesis, Paris Est, 2016. http://www.theses.fr/2016PESC1036/document.
Full textAbstract:
L'étude des ensembles de mots complexité linéaire joue un rôle très important dans la théorie de combinatoire des mots et dans la théorie des systèmes dynamiques symboliques.Cette famille d'ensembles comprend les ensembles de facteurs : d'un mot Sturmien ou d'un mot d'Arnoux-Rauzy, d'un codage d'échange d'intervalle, d'un point fixe d'un morphisme primitif, etc.L'enjeu principal de cette thèse est l'étude de systèmes dynamiques minimales, définis de façon équivalente comme ensembles factoriels de mots uniformément récurrents.Comme résultat principal nous considérons une hiérarchie naturelle de systèmes minimal contenante les ensembles neutres, les tree sets et les ensembles spéculaires.De plus, on va relier ces systèmes au groupe libre en utilisant les mots de retours et les bases de sous-groupes d'indice fini.L'on étude aussi les systèmes symboliques dynamiques engendrés par les échanges d'intervalle et les involutions linéaires, ce qui nous permet d'obtenir des exemples et des interprétations géométriques des familles d'ensembles que définis dans notre hiérarchie.L'un des principal outil utilisé ici est l'étude des extensions possibles d'un mot dans un ensemble, ce qui nous permet de déterminer des propriétés telles que la complexité factorielle.Dans ce manuscrit, nous définissons le graphe d'extension, un graphe non orienté associé à chaque mot $w$ dans un ensemble $S$ qui décrit les extensions possibles de $w$ dans $S$ à gauche et à droite.Dans cette thèse, nous présentons plusieurs classes d'ensembles de mots définis par les formes possibles que les graphes d'extensions des éléments dans l'ensemble peuvent avoir.L'une des conditions les plus faibles que nous allons étudier est la condition de neutralité: un mot $w$ est neutre si le nombre de paires $(a,b)$ de lettres telles que $awb in S$ est égal au nombre de lettres $a$ tel que $aw in S$ plus le nombre de lettres $b$ tel que $wb in S$ moins 1.Un ensemble tel que chaque mot non vide satisfait la condition de neutralité est appelé un ensemble neutre.Une condition plus forte est la condition de l'arbre: un mot $w$ satisfait cette condition si son graphe d'extension est à la fois acyclique et connecté.Un ensemble est appelé un tree set si tout mot non vide satisfait cette condition.La famille de tree sets récurrents apparaît comme fermeture naturelle de deux familles d'ensembles très importants : les facteurs d'un mot d'Arnoux-Rauzy et les ensembles d'échange d'intervalle.Nous présentons également les ensembles spéculaires, une sous-famille remarquable de tree sets.Il s'agit également de sous-ensembles de groupes qui forment une généralisation naturelle des groupes libres.Ces ensembles de mots sont une généralisation abstraite des codages naturelles d'échanges d'intervalle et d'involutions linéaires.Pour chaque classe d'ensembles considéré dans cette thèse, nous montrons plusieurs résultats concernant les propriétés de fermeture (sous décodage maximale bifixe ou par rapport aux mots dérivés), la cardinalité des codes bifixes et les de mots de retour, la connexion entre mots de retour et bases du groupe libre, ainsi qu'entre les codes bifixes et les sous-groupes du groupe libre.Chacun de ces résultats est prouvé en utilisant les hypothèses les plus faibles possiblesSets of words of linear complexity play an important role in combinatorics on words and symbolic dynamics.This family of sets includes set of factors of Sturmian and Arnoux-Rauzy words, interval exchange sets and primitive morphic sets, that is, sets of factors of fixed points of primitive morphisms.The leading issue of this thesis is the study of minimal dynamical systems, also defined equivalently as uniformly recurrent sets of words.As a main result, we consider a natural hierarchy of minimal systems containing neutral sets, tree sets and specular sets.Moreover, we connect the minimal systems to the free group using the notions of return words and basis of subroups of finite index.Symbolic dynamical systems arising from interval exchanges and linear involutions provide us geometrical examples of this kind of sets.One of the main tool used here is the study of possible extensions of a word in a set, that allows us to determine properties such as the factor complexity.In this manuscript we define the extension graph, an undirected graph associated to each word $w$ in a set $S$ which describes the possible extensions of $w$ in $S$ on the left and the right.In this thesis we present several classes of sets of words defined by the possible shapes that the graphs of elements in the set can have.One of the weakest condition that we will study is the neutrality condition: a word $w$ is neutral if the number of pairs $(a, b)$ of letters such that $awb in S$ is equal to the number of letters $a$ such that $aw in S$ plus the number of letters $b$ such that $wb in S$ minus 1.A set such that every nonempty word satisfies the neutrality condition is called a neutral set.A stronger condition is the tree condition: a word $w$ satisfies this condition if its extension graph is both acyclic and connected.A set is called a tree set if any nonempty word satisfies this condition.The family of recurrent tree sets appears as a the natural closure of two known families, namely the Arnoux-Rauzy sets and the interval exchange sets.We also introduce specular sets, a remarkable subfamily of the tree sets.These are subsets of groups which form a natural generalization of free groups.These sets of words are an abstract generalization of the natural codings of interval exchanges and of linear involutions.For each class of sets considered in this thesis, we prove several results concerning closure properties (under maximal bifix decoding or under taking derived words), cardinality of the bifix codes and set of return words in these sets, connection between return words and basis of the free groups, as well as between bifix codes and subgroup of the free group.Each of these results is proved under the weakest possible assumptions
13
Blondin, Massé Alexandre. "A l'intersection de la combinatoire des mots et de la géométrie discrète : palindromes, symétries et pavages." Thesis, Grenoble, 2011. http://www.theses.fr/2011GRENM072/document.
Full textAbstract:
Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentésIn this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in codings of rotations, a family of words including the famous Sturmian words and Rote sequences. In particular, we show that these words are full, i.e. they realize the maximal palindromic complexity. Next, we consider a new family of words called generalized pseudostandard words, which are generated by an operator called iterated pseudopalindromic closure. We present a generalization of a formula described by Justin which allows one to generate in linear (thus optimal) time a generalized pseudostandard word. The central object, the f-palindrome or pseudopalindrome, is an indicator of the symmetries in geometric objects. In the last chapters, we focus on geometric problems. More precisely, we solve two conjectures of Provençal about tilings by translation, by exploiting the presence of palindromes and local periodicity in boundary words. At the end of many chapters, different open problems and conjectures are briefly presented
14
Béaur, Pierre. "Algorithmique et combinatoire des mots par les représentations S-adiques." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASG033.
Full textAbstract:
En combinatoire des mots, une méthode classique de construction de mots infinis est le modèle substitutif. Il consiste à itérer infiniment une transformation (une substitution) sur une lettre initiale. Le modèle substitutif a permis de créer et d'étudier des mots infinis possédant des structures répétitives fortes mais non périodiques. Introduites à la fin des années 1990, les représentations S-adiques forment une extension classique du modèle substitutif. Dans le modèle S-adique, plutôt qu'itérer une seule et même substitution, il est possible de choisir une substitution à chaque itération dans un ensemble fini. Les représentations S-adiques ont originellement été établies à des fins dynamiques, et caractérisent plusieurs familles classiques de mots comme les mots Sturmiens qui n'étaient pas complètement capturées par le modèle substitutif. Cette thèse s'intéresse à l'utilisation des représentations S-adiques à des fins combinatoires et algorithmiques.Dans une première partie, je propose une application dans le cadre de la théorie des ω-automates. L'objectif est de décider si un ω-automate faible accepte un mot Sturmien. Je développe une méthode, la désubstitution d'automates, qui permet de résoudre cette question, et de donner des propriétés combinatoires des ω-automates acceptant un mot Sturmien. Ces méthodes peuvent être généralisées à d'autres constructions substitutives (mot purement substitutif, point fixe d'une substitution) et aux autres familles de mots admettant une caractérisation S-adique. Il est possible d'utiliser ces méthodes pour résoudre différents problèmes annexes, comme le codage d'un mot Sturmien, ou, en géométrie discrète, le recollement de segments discrets. La deuxième partie est consacrée à l'étude des pièges à facteurs sur les mots bi-infinis. Elle résulte d'un travail collaboratif avec Hellouin et Gheeraert. Les pièges à facteurs viennent de la théorie de la compression, et sont un objet combinatoire permettant de mesurer la répétitivité d'un mot. Dans le cas mono-infini, seuls les mots ultimement périodiques admettent des pièges à facteurs finis. Nous prouvons que dans le cas bi-infini, ce résultat ne tient plus : nous exhibons et caractérisons les mots bi-infinis apériodiques admettant des pièges à facteurs finis. Il s'agit des mots Sturmiens caractéristiques, de leurs décalages finis, et de leurs images par des substitutions apériodiques. Nos méthodes reposent sur la caractérisation S-adique des mots Sturmiens, et consiste principalement en une adaptation de la désubstitution aux pièges à facteurs. Dans la troisième et dernière partie, j'explore les possibilités combinatoires des représentations S-adiques dans de nouveaux espaces. Je prouve que deux modèles exotiques de représentations S-adiques, les modèles d'Aubrun-Sablik et de Baraviera-Leplaideur, respectivement sur ℕᵈ et sur le monoïde libre à deux éléments, ne peuvent pas représenter toute configuration : ils ne sont pas universels. Enfin, j'étudie une variante du problème du domino, appelée le problème du X-domino, paramétré par un sous-shift ou une famille de mots X. Le but est d'appréhender la frontière d'indécidabilité entre une et deux dimensions. Je m'intéresse au cas où X est un sous-shift minimal, puis j'explore le cas des mots Sturmiens et des mots sans carréIn combinatorics on words, a classical method to construct infinite words is the substitutive model. It consists in iterating infinitely an operation (a substitution) on an initial letter. The substitutive model has made it possible to create and study infinite words exhibiting some repetitive structures that are still aperiodic. Introduced in the late 1990s, S-adic representations are a classical extension of the substitutive model. In the S-adic model, at each iteration, rather than always iterate a single substitution, one can iterate a substitution chosen in a finite set. S-adic representations were originally established for dynamic purposes, and characterize several classical word families such as Sturmian words, that were not fully captured by the substitutive model. This thesis focuses on the use of S-adic representations for combinatorial and algorithmic purposes. In a first part, I propose an application in the framework of ω-automata theory. The objective is to decide whether a weak ω-automaton accepts a Sturmian word. I develop a method, called automata desubstitution, that solves this question, and gives combinatorial properties of ω-automata accepting a Sturmian word. These methods can be generalized to other substitutive constructions (purely substitutive word, fixed point of a substitution) and to other word families admitting an S-adic characterization. These methods can be used to solve a number of related problems, such as the encoding of a Sturmian word or, in discrete geometry, the reconnection of discrete segments. The second part is devoted to the study of string attractors on bi-infinite words. It is the result of a collaboration with Hellouin and Gheeraert. String attractors come from text compression theory, and are a combinatorial object for measuring the repetitiveness of a word. In the mono-infinite case, only ultimately periodic words admit finite string attractors. We prove that in the bi-infinite case, this result no longer holds: we exhibit and characterize bi-infinite aperiodic words admitting finite string attractors. These are the characteristic Sturmian words, their finite shifts, and their images by aperiodic substitutions. Our methods are based on the S-adic characterization of Sturmian words, and consist mainly in an adaptation of desubstitution to string attractors.In the third and final part, I explore the combinatorial possibilities of S-adic representations in new spaces.I prove that two exotic models of S-adic representations, the Aubrun-Sablik and Baraviera-Leplaideur models, on ℕᵈ and the free monoid on two elements respectively, cannot represent every configuration: they are not universal. Finally, I study a variant of the domino problem, called the X-domino problem, parameterized by a subshift or a family of words X. The aim is to understand the undecidability boundary between one and two dimensions. I focus on the case where X is a minimal subshift, and then explore the case of Sturmian words and squarefree words
15
Sacomoto, Gustavo Akio Tominaga. "Árvores de Ukkonen: caracterização combinatória e aplicações." Universidade de São Paulo, 2011. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-21042011-092209/.
Full textAbstract:
A árvore de sufixos é uma estrutura dados, que representa em espaço linear todos os fatores de uma palavra, com diversos exemplos de aplicações práticas. Neste trabalho, definimos uma estrutura mais geral: a árvore de Ukkonen. Provamos para ela diversas propriedades combinatórias, dentre quais, a minimalidade em um sentido preciso. Acreditamos que a apresentação aqui oferecida, além de mais geral que as árvores de sufixo, tem a vantagem de oferecer uma descrição explícita da topologia da árvore, de seus vértices, arestas e rótulos, o que não vimos em nenhum outro trabalho. Como aplicações, apresentamos também a árvore esparsa de sufixos (que armazena apenas um subconjunto dos sufixos) e a árvore de k-fatores (que armazena apenas os segmentos de comprimento k, ao invés dos sufixos) definidas como casos particulares das árvores de Ukkonen. Propomos para as árvores esparsas um novo algoritmo de construção com tempo O(n) e espaço O(m), onde n é tamanho da palavra e m é número de sufixos. Para as árvores de k-fatores, propomos um novo algoritmo online com tempo e espaço O(n), onde n é o tamanho da palavra.The suffix tree is a data structure that represents, in linear space, all factors of a given word, with several examples of practical applications. In this work, we define a more general structure: the Ukkonen\'s tree. We prove many properties for it, among them, its minimality in a precise sense. We believe that this presentation, besides being more general than the suffix trees, has the advantage of offering an explicit description of the tree topology, its vertices, edges and labels, which was not seen in any other work. As applications, we also presents the sparse suffix tree (which stores only a subset of the suffixes) and the k-factor tree (which stores only the substrings of length k, instead of the suffixes), both defined as Ukkonen\'s tree special cases. We propose a new construction algorithm for the sparse suffix trees with time O(n) and space O(m), where n is the size of the word and m is the number of suffixes. For the k-factor trees, we propose a new online algorithm with time and space O(n), where n is the size of the word.
16
Heuer, Manuela. "Combinatorial aspects of root lattices and words." Thesis, Open University, 2010. http://oro.open.ac.uk/24046/.
Full textAbstract:
This thesis is concerned with two topics that are of interest for the theory of aperiodic order. In the first part, the similar sublattices and coincidence site lattices of the root lattice A4 are analysed by means of a particular quaternion algebra. Dirichlet series generating functions are derived, which count the number of similar sublattices, respectively coincidence site lattices, of each index. In the second part, several strategies to derive upper and lower bounds for the entropy of certain sets of powerfree words are presented. In particular, Kolpakov's arguments for the derivation of lower bounds for the entropy of powerfree words are generalised. For several explicit sets we derive very good upper and lower bounds for their entropy. Notably, Kolpakov's lower bounds for the entropy of ternary squarefree, binary cubefree and ternary minimally repetitive words are confirmed exactly.
17
Vaslet, Elise. "Répétitions dans les mots et seuils d'évitabilité." Thesis, Aix-Marseille 2, 2011. http://www.theses.fr/2011AIX22048/document.
Full textAbstract:
Nous étudions dans cette thèse différents problèmes d'évitabilité des répétitions dans les mots infinis. Soulevée par Thue et motivée par ses travaux sur les mots sans carrés, la problématique s'est développée au cours du XXe siècle, et est aujourd'hui devenue un des grands domaines de recherche en combinatoire des mots. En 1972, Dejean proposa une importante conjecture, dont la validation étape par étape s'est terminée récemment (2009). La conjecture concerne le seuil des répétitions d'un alphabet, i.e., la borne inférieure des exposants évitables sur cet alphabet. La notion de seuil, comme frontière entre évitabilité et non-évitabilité d'un ensemble donné de mots, est le fil directeur de nos travaux. Nous nous intéressons d'abord à une généralisation du seuil des répétitions (nous donnons des encadrements de sa valeur). Cette notion permet d'ajouter, pour décrire l'ensemble des répétitions à éviter, au paramètre de l'exposant, celui de la longueur des répétitions. Puis, nous étudions des problèmes d'existence de mots dans lesquels, simultanément, certaines répétitions sont interdites et d'autres sont forcées. Nous répondons, pour l'alphabet ternaire, à la question : quels réels sont l'exposant critique d'un mot infini sur un alphabet fixé? Nous introduisons ensuite une notion de haute répétitivité, et établissons une description partielle des couples d'exposants paramètrant une double contrainte de haute répétitivité et d'évitabilité. Pour finir, nous utilisons des résultats et techniques issus de ces problématiques pour résoudre une question de coloration de graphes : nous introduisons un seuil des répétitions, calqué sur celui connu pour les mots, et donnons sa valeur pour deux classes de graphes, les arbres et les graphes de subdivisionsIn this thesis we study various problems on repetition avoidance in infinite words. Raised by Thue and motivated by his work on squarefree words, the topic developed during the 20th century, and has nowadays become a principal area of research in combinatorics on words. In 1972, Dejean proposed an important conjecture whose verification in steps was completed recently (2009). The conjecture concerns the repetition threshold for an alphabet, i.e., the infimum of the avoidable exponents for that alphabet. The notion of threshold as a borderline between avoidability and unavoidability for a given set of words is the guiding line of our work. First, we focus on a generalization of the repetition threshold. This concept allows us to include, in addition to the exponent, the length of the repetitions as a parameter in the description of the set of repetitions to avoid. We obtain various bounds in that respect. We then study existence problems for words in which simultaneously some repetitions are forbidden, and others are forced. For the ternary alphabet, we answer the question: what real numbers are the critical exponent of some infinite word over a given alphabet? Also, we introduce a notion of highly repetitive words and give a partial description of the pairs of exponents which parameterize the existence of words both highly repetitive and repetition-free. Finally, we use results and techniques stemming from those problems to solve a question on graph colouring: we introduce a repetition threshold adapted from the thresholds we know for words, and give its value for two classes of graphs, namely, trees and subdivision graphs
18
Tahay, Pierre-Adrien. "Colonnes dans les automates cellulaires et suites généralisées de Rudin-Shapiro." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0198.
Full textAbstract:
Cette thèse se situe à la frontière entre mathématiques et informatique théorique. Nous nous intéressons dans un premier temps aux automates finis et aux automates cellulaires. Bien qu’ils s’agissent de deux objets mathématiques assez différents, il est possible de les relier par des constructions explicites, en regardant la réalisation des suites automatiques dans les diagrammes espace-temps des automates cellulaires. Dans un second temps, nous étudions les corrélations discrètes de certaines suites automatiques, appelées suites généralisées de Rudin–Shapiro, qui se comportent comme des suites aléatoires pour la corrélation discrète d’ordre 2, bien qu’elles soient déterministes. Après une introduction des objets d’étude, que nous illustrons par plusieurs exemples, nous rappelons le résultat de Rowland et Yassawi, qui ont montré en 2015 qu’il était possible de construire de manière explicite toute suite p-automatique, dans le cas où p est un nombre premier, en colonne d’un automate cellulaire linéaire, à partir d’une configuration initiale finie. En utilisant leur méthode, nous obtenons différentes constructions de suites automatiques de référence, puis nous établissons un moyen explicite de construire toute une famille de suites p-automatiques, appelées suites généralisées de Rudin–Shapiro, que nous étudions dans la deuxième partie de la thèse, dans un cadre plus général. Nous nous intéressons également au cas de certaines suites non-automatiques, telles que l’indicatrice des polynômes et le mot de Fibonacci, que nous réussissons à construire en colonne d’automates cellulaires non-linéaires. Puis nous obtenons des résultats sur des recodages binaires, permettant de réduire le nombre de symboles dans les automates cellulaires. Grâce à un recodage binaire, nous avons également construit explicitement une suite 3-automatique sur un alphabet binaire, en colonne d’un automate cellulaire à 2 états, non-périodique à partir d’un certain rang, ce qui répond à une question posée par Rowland et Yassawi. Dans la deuxième partie de cette thèse, nous reprenons les travaux de Grant, Shallit et Stoll, qui ont établi en 2009 des résultats sur les corrélations discrètes de suites infinies sur des alphabets finis. En exploitant les propriétés de récursivité de la suite classique de Rudin–Shapiro, ils construisent une famille de suites déterministes sur des alphabets plus grands, pour lesquelles ils montrent que dans le cas où la taille de l’alphabet est sans facteur carré, la moyenne empirique des coefficients de corrélation d’ordre 2 a la même limite que dans le cas de suites où les lettres sont tirées aléatoirement, de manière uniforme et indépendamment. De plus, ils arrivent à quantifier explicitement le terme d’erreur. En généralisant leur construction à l’aide de la théorie des matrices de différence, nous arrivons à établir un résultat similaire pour des alphabets de taille quelconque ainsi qu’une amélioration du terme d’erreur dans certains cas. Tout comme Grant et al., nous nous servons de la théorie des sommes d’exponentielles pour démontrer notre résultat sur les corrélations discrètes d’ordre 2 de nos suites généralisées de Rudin–Shapiro. Dans la troisième partie, nous terminons par une approche combinatoire de ces questions, qui nous a permis d’obtenir une amélioration du terme d’erreur dans le cas où la taille de l’alphabet est un produit d’au moins deux nombres premiers distincts, et de généraliser certains de nos résultatsThis thesis is at the interface between mathematics and theoretical computer science. In the first part, our main objects are finite automata and cellular automata. While relatively different in nature, it is possible to link both by explicit constructions. More specifically, it is possible to realise automatic sequences in the space-time diagrams of cellular automata. In the second part, we study discrete correlation properties of so-called generalised Rudin–Shapiro sequences. These are automatic sequences, hence deterministic, but show similar properties as random sequences with respect to their discrete correlation of order 2. After introducing the objects of study, illustrated by several examples, we first recall the result of Rowland and Yassawi. They showed in 2015 via an algebraic approach that it is possible to construct explicitly any p-automatic sequence (p is a prime number) as a column of a linear cellular automaton with a finite initial configuration. By using their method, we obtain several constructions of classical automatic sequences, and an explicit way to build a family of p-automatic sequences that we study in a more general context in the second part of the thesis. We also investigate several non-automatic sequences, such as the characteristic sequence of integer-valued polynomials and the Fibonacci word, which both can be realised as columns of non-linear cellular automata. We end this part by some results about binary recodings in order to reduce the number of symbols in the cellular automata. Under a binary recoding, we give explicitly a 3-automatic sequence on a binary alphabet, as a column of a cellular automaton with 2 states, that is not eventually periodic. This answers a question asked by Rowland et Yassawi. In the second part of the thesis, we take up research from 2009 of Grant, Shallit, and Stoll about discrete correlations of infinite sequences over finite alphabets. By using the recursivity properties of the classical Rudin–Shapiro sequence, they built a family of deterministic sequences over larger alpha- bets, called generalised Rudin–Shapiro sequences, for which they showed that when the size of the alphabet is squarefree, the empirical means of the discrete correlation coefficients of order 2 have the same limit as in the case of random sequences where each letter is independently and uniformly chosen. Moreover, they gave explicit error terms. We extend their construction by means of difference matrices and establish a similar result on alphabets of arbitrary size. On our way, we obtain an improvement of the error term in some cases. The methods stem, as those used by Grant et al., from the theory of exponential sums. In the third part, we use a more direct combinatorial approach to study correlations. This allows for an improvement of the error term when the size of the alphabet is a product of at least two distinct primes, and allows to generalise some of our results of the second part
19
Mancini, Ilaria. "Combinatorial problems concerning words defined by morphisms and polyominoes satisfying convexity constraints." Doctoral thesis, Università di Siena, 2022. http://hdl.handle.net/11365/1193623.
Full textAbstract:
One of the main subfields of combinatorics is combinatorics on words. This work concerns the study of the Burrows-Wheeler transform (BWT) when applied to morphic words. The BWT is a popular method used for text compression, because it produces a permutation of the characters of an input word and tends to group the same characters together. We restrict our investigation to binary morphic words. The main result is that for a binary morphism µ with quadratic factorial complexity, the number of clusters of the output word ρ(bwt(µ^i(a))) is O(i), from which follows that every binary morphism is BWT-compressible. We believe that such techniques can be extended to other classes of morphisms and, consequently, this bound O(i) may also hold independently of the factorial complexity. Moreover, we are interested to characterize the morphisms for which the bound becomes Θ(i), to extend it to words on larger alphabets.
Another of the main subfields of combinatorics is enumerative combinatorics. This work is about the enumeration of classes of polyominoes defined by convexity constraints by using bijective methods. We present a correspondences between directed convex polyominoes and triplets (F, G, λ), where F, G are ordered forests and λ is a monotone path, called cut. By using this correspondence and by imposing some constraints on the trees and/or on the cut, we get the enumeration of directed k-convex polyominoes with respect to their semi-perimeter for each k ≥ 1. Our porpouse is to extend this method to solve the still open problem of enumerating k-convex polyominoes with k ≥ 3.
We have investigated the class C(k,1) of polyominoes with NE-degree of convexity equal to k and we have proved that there exists a bijection between C(k,1) polyominoes and pairs of forests with pairs of cuts. We also provide a decomposition of the class of C(k,1) polyominoes into subclasses obtained from k or (k+1)-parallelogram polyominoes by some particular cuts and we show a correspondence between the cells of a polyomino and the nodes of its associated pair of forests, with the purpouse of characterizing the lower cut. We believe that the method to enumerate directed k-convex polyominoes could be generalized and used to get the enumeration of C(k,1) polyominoes and, consequently, of all k-convex polyominoes.
20
Wilson, Nancy. "Ars combinatoria in selected works of C.P.E. Bach : an analytic investigation." Thesis, McGill University, 1988. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=61758.
Full text
21
Sjöstrand, Jonas. "Enumerative combinatorics related to partition shapes." Doctoral thesis, KTH, Matematik (Inst.), 2007. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-4298.
Full textAbstract:
This thesis deals with enumerative combinatorics applied to three different objects related to partition shapes, namely tableaux, restricted words, and Bruhat intervals. The main scientific contributions are the following. Paper I: Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2^[n/2]. We prove a generalisation of this conjecture using the Robinson-Schensted correspondence and a new concept called chess tableaux. The proof is built on a remarkably simple relation between the sign of a permutation pi and the signs of its RS-corresponding tableaux P and Q, namely sgn(pi) = (−1)^v sgn(P)sgn(Q), where v is the number of disjoint vertical dominoes that fit in the partition shape of P and Q. The sign-imbalance of a partition shape is defined as the sum of the signs of all standard Young tableaux of that shape. As a further application of the sign-transferring formula above, we also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. Paper II: We generalise some of the results in paper I to skew tableaux. More precisely, we examine how the sign property is transferred by the skew Robinson-Schensted correspondence invented by Sagan and Stanley. The result is a surprisingly simple generalisation of the ordinary non-skew formula above. As an application, we find vanishing weighted sums of squares of sign-imbalances, thereby generalising a variant of Stanley’s second conjecture. Paper III: The following special case of a conjecture by Loehr and Warrington was proved by Ekhad, Vatter, and Zeilberger: There are 10^n zero-sum words of length 5n in the alphabet {+3,−2} such that no consecutive subword begins with +3, ends with −2, and sums to −2. We give a simple bijective proof of the conjecture in its original and more general setting where 3 and 2 are replaced by any relatively prime positive integers a and b, 10^n is replaced by ((a+b) choose a)^n, and 5n is replaced by (a+b)n. To do this we reformulate the problem in terms of cylindrical lattice walks which can be interpreted as the south-east border of certain partition shapes. Paper IV: We characterise the permutations pi such that the elements in the closed lower Bruhat interval [id,pi] of the symmetric group correspond to non-capturing rook configurations on a skew Ferrers board. These intervals turn out to be exactly those whose flag manifolds are defined by inclusions, as defined by Gasharov and Reiner. The characterisation connects Poincaré polynomials (rank-generating functions) of Bruhat intervals with q-rook polynomials, and we are able to compute the Poincaré polynomial of some particularly interesting intervals in the finite Weyl groups A_n and B_n. The expressions involve q-Stirling numbers of the second kind, and for the group A_n putting q = 1 yields the poly-Bernoulli numbers defined by Kaneko.Ämnet för denna avhandling är enumerativ kombinatorik tillämpad på tre olika objekt med anknytning till partitionsformer, nämligen tablåer, begränsade ord och bruhatintervall. Dom viktigaste vetenskapliga bidragen är följande. Artikel I: Låt tecknet av en standardtablå vara tecknet hos permutationen man får om man läser tablån rad för rad från vänster till höger, som en bok. En förmodan av Richard Stanley säjer att teckensumman av alla standardtablåer med n rutor är 2^[n/2]. Vi visar en generalisering av denna förmodan med hjälp av Robinson-Schensted-korrespondensen och ett nytt begrepp som vi kallar schacktablåer. Beviset bygger på ett anmärkningsvärt enkelt samband mellan tecknet hos en permutation pi och tecknen hos dess RS-motsvarande tablåer P och Q, nämligen sgn(pi)=(-1)^v sgn(P)sgn(Q), där v är antalet disjunkta vertikala dominobrickor som får plats i partitionsformen hos P och Q. Teckenobalansen hos en partitionsform definieras som teckensumman av alla standardtablåer av den formen. Som en ytterligare tillämpning av formeln för teckenöverföring ovan bevisar vi också en starkare variant av en annan förmodan av Stanley som handlar om viktade summor av kvadrerade teckenobalanser. Artikel II: Vi generaliserar några av resultaten i artikel I till skeva tablåer. Närmare bestämt undersöker vi hur teckenegenskapen överförs av Sagan och Stanleys skeva Robinson-Schensted-korrespondens. Resultatet är en förvånansvärt enkel generalisering av den vanliga ickeskeva formeln ovan. Som en tillämpning visar vi att vissa viktade summor av kvadrerade teckenobalanser blir noll, vilket leder till en generalisering av en variant av Stanleys andra förmodan. Artikel III: Följande specialfall av en förmodan av Loehr och Warrington bevisades av Ekhad, Vatter och Zeilberger: Det finns 10^n ord med summan noll av längd 5n i alfabetet {+3,-2} sådana att inget sammanhängande delord börjar med +3, slutar med -2 och har summan -2. Vi ger ett enkelt bevis för denna förmodan i dess ursprungliga allmännare utförande där 3 och 2 byts ut mot vilka som helst relativt prima positiva heltal a och b, 10^n byts ut mot ((a+b) över a)^n och 5n mot (a+b)n. För att göra detta formulerar vi problemet i termer av cylindriska latticestigar som kan tolkas som den sydöstra gränslinjen för vissa partitionsformer. Artikel IV: Vi karakteriserar dom permutationer pi sådana att elementen i det slutna bruhatintervallet [id,pi] i symmetriska gruppen motsvarar ickeslående tornplaceringar på ett skevt ferrersbräde. Dessa intervall visar sej vara precis dom vars flaggmångfalder är definierade av inklusioner, ett begrepp introducerat av Gasharov och Reiner. Karakteriseringen skapar en länk mellan poincarépolynom (ranggenererande funktioner) för bruhatintervall och q-tornpolynom, och vi kan beräkna poincarépolynomet för några särskilt intressanta intervall i dom ändliga weylgrupperna A_n och B_n. Uttrycken innehåller q-stirlingtal av andra sorten, och sätter man q=1 för grupp A_n så får man Kanekos poly-bernoullital.
QC 20100818
22
Akin, Banu. "Approaches For Special Multiobjective Combinatorial Optimization Problems With Side Constraints." Master's thesis, METU, 2012. http://etd.lib.metu.edu.tr/upload/12614603/index.pdf.
Full textAbstract:
We propose a generic algorithm based on branch-and-bound to generate all efficient solutions of multiobjective combinatorial optimization (MOCO) problems. We present an algorithm specific to multiobjective 0-1 Knapsack Problem based on the generic algorithm. We test the performance of our algorithm on randomly generated sample problems against IBM ILOG CPLEX and we obtain better performance using a problem specific algorithm. We develop a heuristic algorithm by incorporating memory limitations at the expense of solution quality to overcome memory issues of the exact algorithm.
23
Burns, Jonathan. "Recursive Methods in Number Theory, Combinatorial Graph Theory, and Probability." Scholar Commons, 2014. https://scholarcommons.usf.edu/etd/5193.
Full textAbstract:
Recursion is a fundamental tool of mathematics used to define, construct, and analyze mathematical objects. This work employs induction, sieving, inversion, and other recursive methods to solve a variety of problems in the areas of algebraic number theory, topological and combinatorial graph theory, and analytic probability and statistics. A common theme of recursively defined functions, weighted sums, and cross-referencing sequences arises in all three contexts, and supplemented by sieving methods, generating functions, asymptotics, and heuristic algorithms.
In the area of number theory, this work generalizes the sieve of Eratosthenes to a sequence of polynomial values called polynomial-value sieving. In the case of quadratics, the method of polynomial-value sieving may be characterized briefly as a product presentation of two binary quadratic forms. Polynomials for which the polynomial-value sieving yields all possible integer factorizations of the polynomial values are called recursively-factorable. The Euler and Legendre prime producing polynomials of the form n2+n+p and 2n2+p, respectively, and Landau's n2+1 are shown to be recursively-factorable. Integer factorizations realized by the polynomial-value sieving method, applied to quadratic functions, are in direct correspondence with the lattice point solutions (X,Y) of the conic sections aX2+bXY +cY2+X-nY=0. The factorization structure of the underlying quadratic polynomial is shown to have geometric properties in the space of the associated lattice point solutions of these conic sections.
In the area of combinatorial graph theory, this work considers two topological structures that are used to model the process of homologous genetic recombination: assembly graphs and chord diagrams. The result of a homologous recombination can be recorded as a sequence of signed permutations called a micronuclear arrangement. In the assembly graph model, each micronuclear arrangement corresponds to a directed Hamiltonian polygonal path within a directed assembly graph. Starting from a given assembly graph, we construct all the associated micronuclear arrangements. Another way of modeling genetic rearrangement is to represent precursor and product genes as a sequence of blocks which form arcs of a circle. Associating matching blocks in the precursor and product gene with chords produces a chord diagram. The braid index of a chord diagram can be used to measure the scope of interaction between the crossings of the chords. We augment the brute force algorithm for computing the braid index to utilize a divide and conquer strategy. Both assembly graphs and chord diagrams are closely associated with double occurrence words, so we classify and enumerate the double occurrence words based on several notions of irreducibility. In the area of analytic probability, moments abstractly describe the shape of a probability distribution. Over the years, numerous varieties of moments such as central moments, factorial moments, and cumulants have been developed to assist in statistical analysis. We use inversion formulas to compute high order moments of various types for common probability distributions, and show how the successive ratios of moments can be used for distribution and parameter fitting. We consider examples for both simulated binomial data and the probability distribution affiliated with the braid index counting sequence. Finally we consider a sequence of multiparameter binomial sums which shares similar properties with the moment sequences generated by the binomial and beta-binomial distributions. This sequence of sums behaves asymptotically like the high order moments of the beta distribution, and has completely monotonic properties.
24
Angeleska, Angela. "Combinatorial models for DNA rearrangements in ciliates." [Tampa, Fla] : University of South Florida, 2009. http://purl.fcla.edu/usf/dc/et/SFE0002998.
Full text
25
White, Bradley Michael. "Experimental Development of Automated Search Techniques for Discrete Combinatorial Optimisation." Thesis, Griffith University, 2009. http://hdl.handle.net/10072/365420.
Full textAbstract:
A suite of techniques for finding the optimal solutions for a set of discrete combinatorial problems was developed. An experimental approach was used, with a suitable test-bed found in a class of word-puzzles.
The crux of such research is that seeking optimal solutions to discrete combinatorial problems requires the use of deterministic algorithms. Attention was focused on the development of new techniques capable of exhausting the search space more efficiently. Although research was restricted to tractable problems, exhaustion of the search space was recognised to be practically infeasible for all but small problem instances. Thus the size and complexity of the problems examined was necessarily restricted.
On these grounds the selection of an appropriate test-bed was fundamental to the research. Complex word problems were used because they encompass a wide range of discrete combinatorial problems, but have only a small literature. The specific puzzle examples employed as test-beds had all been used in public competitions with solutions submitted by thousands of humans, with the winning solutions and scores published. This allowed a simple and independent initial benchmark of success. The techniques developed could be judged to be at least partially successful in that they were able to at least equal and in some cases beat the highest recorded scores. The general problem of benchmarking is discussed.
It was observed that small changes to the test bed puzzles or to the techniques would often impact dramatically on the results. In an attempt to isolate the reasons for this, a focused view of the search algorithms was adopted. Complex holistic algorithms were broken into smaller sub-algorithmic categories, such as: node selection, domain maintenance, forward tracking, backtracking, branch-and-bound, primary slot selection, variable ordering, value ordering, and constraint ordering. Within each of these categories a range of variations is presented.
Techniques for removing inconsistencies prior to search were also experimented with. These consistency pre-processors were found to have a minimal and at times detrimental effect on search times when a good selection of search techniques was used. However, they were found to offer considerable benefits in instances where a poor selection of search techniques was chosen. As such these consistency pre-processors may be viewed as useful in terms of a risk management strategy for solving these problems.
Whilst not the primary focus of this research experimentation with stochastic techniques within a deterministic framework was performed. The purpose of which was to gauge the impact of generating good solutions prior to an exhaustive search. A technique developed was observed to frequently improve the time taken to form an optimal solution, and improve the total time taken to exhaust the search space.
While the major effort in the research was necessarily spent in developing and testing these algorithms and their implementations, specific attention was paid to the methodological problems inherent in experimental approaches to program development.Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Griffith Business School
Griffith Business School
Full Text
26
Milker, Joseph Alan. "Move-Count Means with Cancellation and Word Selection Problems in Rubik's Cube Solution Approaches." Kent State University / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=kent1343073076.
Full text
27
Wojcik, Caius. "Factorisations des mots de basse complexité." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1340.
Full textAbstract:
Nous présentons dans ce doctorat de mathématiques le travail effectué pendant trois ans à l'Université Claude Bernard Lyon 1. Ce doctorat a été réalisé sous les directions de Boris Adamczewski et Luca Zamboni, tous deux chercheurs à l'UCBL. Le thème général abordé est la combinatoire des mots, sous la forme de deux contributions, l'une concernant la théorie de Ramsey développée dans la première partie, et l'autre la classe des mots sturmiens développée dans la seconde partie. La combinatoire des mots est un domaine à la croisée des mathématiques, et plus généralement des sciences. Avec l'essor de l'informatique théorique, ou encore des progrès de la génétique, l'étude des suites de symboles est devenu un sujet de recherche incontournable à l'importance grandissante. Les mots vus comme suites de symboles sont en effet intrinsèquement soumis à des lois mathématiques d'une profonde subtilité. L'exemple historique d'Axel Thue d'un mot infini sans facteurs carrés sur un alphabet à trois lettres a été un des points de départ de cette théorie, via une construction non-triviale d'un mot infini soumis à une condition pourtant très simple en apparence. Que ce soit dans la structure des décimales des nombre réels, dans les codes informatiques omniprésents dans le fonctionnement des ordinateurs, ou dans notre propre code génétique, la combinatoire des mots fournit un cadre commun pour une étude en profondeur de problématiques actuelles. Le présent doctorat s'inscrit naturellement dans ce processus scientifique. Directement inspiré par les travaux fondateurs d'Axel Thue, nous étudions dans la première partie les conditions d'existence d'objets combinatoires (en outre, des colorations) soumis à des contraintes d'apparence simples, et nous apportons une réponse optimale à une conjecture qui est restée ouverte pendant une décennie. Cette solution exploite les différences et liens entre les notions naturelles de préfixe et de suffixe en combinatoire des mots. Notre seconde partie, quant à elle, étudie une version infinie du système de numération d'Ostrowski, à l'aide des mots de basse complexité donnés par les mots infinis non-ultimement périodiques de plus petite fonction de complexité que sont les mots sturmiens. Construit d'une manière analogue aux nombres p-adiques, le formalisme introduit et développé concernant les intercepts formels en vue de donner une description combinatoire de la classe des mots sturmiens a pour conséquences plusieurs résultats concernant les factorisations de ces mots. Le calcul des compléments étudié à la fin de cette partie montre comment la comparaison des opérations de préfixe et de suffixe peut être utilisée pour obtenir des résultats non-triviaux concernant les factorisations des mots de basse complexitéWe present in this PhD. in Mathematics the work effectuated during three years at the Lyon 1 University Chaude Bernard Lyon 1. This PhD. has been realied under the supervisions of Boris Adamczewki and Luca Zamboni, both researchers in the Lyon 1 University. The general topic is combinatorics on words, in the form of two contributions, one of them on the limits of Ramsey theory in this context developped in the first part, and the second on the links between the Ostrowski numeration system and factorisations of sturmian words. Combinatorics on words is a domain at the intersections of mathematics, and more generally of sciences. With the emergence of theoretical computer science, or of progresses in genetics, the study of sequences of symbols has become a unavoidable research subject of growing importance. Words seen as a sequence of symboles are indeed bound to deep and subtle mathematical laws. The historical example discovered by Axel Thue of an infinite square-free word over a 3-letter alphabet have been the start of this theory, with a non-trivial construction of a specific word submitted to a seemingly very simple condition. Whether it is within the structure of decimals of real numbers, in the code lines everywhere in computers or inside our own genetic information, combinatorics on words gives a comon theoretical set of tools for a deep study of a number of present scientific issues. The present PhD. lands naturally within this scientific process. Directly inspired by the fundamental work of Axel Thue, we study in the first part the condition for the existence of combinatorial objects, colorations, submitted to a monochromatic constraint, and provide an optimal answer to a conjecture that have remained open for 10 years. This solution exploits the differences and links between the notions of prefixes and suffixes in combinatorics on words. In a second part, we study a infinite version of the Ostrowski numeration system, with the use of the low complexity class of words formed by the sturmian words. Built in a similar way as the p-adic number, the introduced and developped formalism on formal intercepts with the purpose of describing combinatorially the class of sturmian words has several consequences with regards to their factorisations. The calculus of complement, presented at the end shows how comparison of the prefix and suffix operations can be used to derived non-trivial results on factorisation of low complecity words
28
Popoli, Pierre. "Suites automatiques et morphiques de grande complexité le long des sous-suites." Electronic Thesis or Diss., Université de Lorraine, 2022. http://www.theses.fr/2022LORR0195.
Full textAbstract:
Cette thèse se situe à l'intersection des mathématiques et de l'informatique théorique. Une suite pseudo-aléatoire, bien qu'engendrée par un algorithme déterministe, possède un comportement proche de celui d'une suite aléatoire. Nous nous intéressons à différentes mesures de complexité pour les suites pseudo-aléatoires. D'un autre côté, les suites automatiques sont des suites non aléatoires. Cependant, certaines sous-suites des suites automatiques, comme les sous-suites polynomiales, sont bien plus aléatoires. Dans la première partie de cette thèse, nous établissons une borne inférieure de la complexité d'ordre maximal de la suite de Thue-Morse et des suites de motifs le long de tout polynôme unitaire, ce qui répond à une question de Sun et Winterhof (2019). Nous étudions ensuite le système de numération de Zeckendorf. Sa fonction somme des chiffres est une suite morphique non-automatique. Nous établissons une borne inférieure de la complexité d'ordre maximal de la suite de Fibonacci-Thue-Morse le long de tout polynôme unitaire. Nous calculons la complexité d'ordre maximal à l'aide du Graphe Acyclique Orienté de Mot (DAWG). Dans la deuxième partie de cette thèse, nous nous intéressons à la somme des chiffres binaire des carrés parfaits. Nous reprenons les travaux de Hare, Laishram et Stoll (2011) qui étudient le problème de déterminer les entiers impairs dont le poids de Hamming est égal à celui de son carré. Nous résolvons ce problème pour la majorité des cas restants et introduisons de nouveaux outils potentiellement utiles à la résolution complète du problème. Nos méthodes combinent la théorie des nombres, la combinatoire des mots et l'informatique. La dernière partie de cette thèse porte sur les corrélations de la suite de Rudin-Shapiro. La corrélation d'ordre 2 est historiquement très étudiée pour cette suite car elle possède un comportement aléatoire bien que la suite soit déterministe. Cependant, des corrélations d'ordre supérieur de cette suite ne possèdent plus ce comportement aléatoire. Dans la lignée des travaux de Aloui, Mauduit et Mkaouar (2021) sur les corrélations de la suite de Thue-Morse le long des nombres premiers, nous établissons un résultat sur les corrélations de la suite de Rudin-Shapiro le long des nombres premiersThe topic of this thesis lies at the interface between mathematics and computer science. A pseudorandom sequence is a sequence generated by a deterministic algorithm that has properties similar to those of a random sequence. We are interested in various complexity measures for these pseudorandom sequences. Automatic and morphic sequences are not random or pseudorandom, but certain subsequences of these sequences, such as polynomial subsequences for instance, are more random than the original sequences. In the first part of the thesis, we establish a lower bound on the maximal order complexity of the Thue-Morse sequence and related sequences along polynomial subsequences. This answers a question of Sun and Winterhof (2019). We then study the problem in the Zeckendorf numeration system. Its sum of digits function is a morphic non-automatic sequence. We establish a lower bound on the maximal order complexity of the Fibonacci-Thue-Morse sequence along unitary polynomials. We calculate the complexity with the help of the Directed Acyclic Word Graph (DAWG). In the second part, we are interested in the binary sum of digits of squares. We take up the work of Hare, Laishram and Stoll (2011) who studied the problem to determine the odd integers whose Hamming weight is the same as the one of their square. We solve the problem in the majority of the remaining cases, and introduce new tools that might be helpful to completely solve the problem. Our methods range from number theory, combinatorics on words to implementations in the area of computer science. In the third part of the thesis, we study the correlations of the Rudin-Shapiro sequence. The correlations of order 2 are well understood for this sequence, the behavior of this sequence is rather random whereas the original sequence is completely deterministic. The correlation of higher orders of this sequence do not show this random behavior. Aloui, Mauduit and Mkaouar (2021) studied the correlation of the Thue-Morse sequence along prime numbers. We provide a result on the correlation of the Rudin-Shapiro sequence along prime numbers
29
Rocha, Eugénio Alexandre Miguel. "Uma Abordagem Algébrica à Teoria de Controlo Não Linear." Doctoral thesis, Universidade de Aveiro, 2003. http://hdl.handle.net/10773/21444.
Full textAbstract:
Doutoramento em MatemáticaNesta tese de Doutoramento desenvolve-se principalmente uma abordagem algébrica à teoria de sistemas de controlo não lineares. No entanto, outros tópicos são também estudados. Os tópicos tratados são os seguidamente enunciados: fórmulas para sistemas de controlo sobre álgebras de Lie livres, estabilidade de um sistema de corpos rolantes, algoritmos para aritmética digital, e equações integrais de Fredholm não lineares. No primeiro e principal tópico estudam-se representações para as soluções de sistemas de controlo lineares no controlo. As suas trajetórias são representadas pelas chamadas séries de Chen. Estuda-se a representação formal destas séries através da introdução de várias álgebras não associativas e técnicas específicas de álgebras de Lie livres. Sistemas de coordenadas para estes sistemas são estudados, nomeadamente, coordenadas de primeiro tipo e de segundo tipo. Apresenta-se uma demonstração alternativa para as coordenadas de segundo tipo e obtêm-se expressões explícitas para as coordenadas de primeiro tipo. Estas últimas estão intimamente ligadas ao logaritmo da série de Chen que, por sua vez, tem fortes relações com uma fórmula designada na literatura por “continuous Baker-Campbell- Hausdorff formula”. São ainda apresentadas aplicações à teoria de funções simétricas não comutativas. É, por fim, caracterizado o mapa de monodromia de um campo de vectores não linear e periódico no tempo em relação a uma truncatura do logaritmo de Chen. No segundo tópico é estudada a estabilizabilidade de um sistema de quaisquer dois corpos que rolem um sobre o outro sem deslizar ou torcer. Constroem-se controlos fechados e dependentes do tempo que tornam a origem do sistema de dois corpos num sistema localmente assimptoticamente estável. Vários exemplos e algumas implementações em Maple°c são discutidos. No terceiro tópico, em apêndice, constroem-se algoritmos para calcular o valor de várias funções fundamentais na aritmética digital, sendo possível a sua implementação em microprocessadores. São também obtidos os seus domínios de convergência. No último tópico, também em apêndice, demonstra-se a existência e unicidade de solução para uma classe de equações integrais não lineares com atraso. O atraso tem um carácter funcional, mostrando-se ainda a diferenciabilidade no sentido de Fréchet da solução em relação à função de atraso.
In this PhD thesis several subjects are studied regarding the following topics: formulas for nonlinear control systems on free Lie algebras, stabilizability of nonlinear control systems, digital arithmetic algorithms, and nonlinear Fredholm integral equations with delay. The first and principal topic is mainly related with a problem known as the continuous Baker-Campbell-Hausdorff exponents. We propose a calculus to deal with formal nonautonomous ordinary differential equations evolving on the algebra of formal series defined on an alphabet. We introduce and connect several (non)associative algebras as Lie, shuffle, zinbiel, pre-zinbiel, chronological (pre-Lie), pre-chronological, dendriform, D-I, and I-D. Most of those notions were also introduced into the universal enveloping algebra of a free Lie algebra. We study Chen series and iterated integrals by relating them with nonlinear control systems linear in control. At the heart of all the theory of Chen series resides a zinbiel and shuffle homomorphism that allows us to construct a purely formal representation of Chen series on algebras of words. It is also given a pre-zinbiel representation of the chronological exponential, introduced by A.Agrachev and R.Gamkrelidze on the context of a tool to deal with nonlinear nonautonomous ordinary differential equations over a manifold, the so-called chronological calculus. An extensive description of that calculus is made, collecting some fragmented results on several publications. It is a fundamental tool of study along the thesis. We also present an alternative demonstration of the result of H.Sussmann about coordinates of second kind using the mentioned tools. This simple and comprehensive proof shows that coordinates of second kind are exactly the image of elements of the dual basis of a Hall basis, under the above discussed homomorphism. We obtain explicit expressions for the logarithm of Chen series and the respective coordinates of first kind, by defining several operations on a forest of leaf-labelled trees. It is the same as saying that we have an explicit formula for the functional coefficients of the Lie brackets on a continuous Baker-Campbell-Hausdorff-Dynkin formula when a Hall basis is used. We apply those formulas to relate some noncommutative symmetric functions, and we also connect the monodromy map of a time-periodic nonlinear vector field with a truncation of the Chen logarithm. On the second topic, we study any system of two bodies rolling one over the other without twisting or slipping. By using the Chen logarithm expressions, the monodromy map of a flow and Lyapunov functions, we construct time-variant controls that turn the origin of a control system linear in control into a locally asymptotically stable equilibrium point. Stabilizers for control systems whose vector fields generate a nilpotent Lie algebra with degree of nilpotency · 3 are also given. Some examples are presented and Maple°c were implemented. The third topic, on appendix, concerns the construction of efficient algorithms for Digital Arithmetic, potentially for the implementation in microprocessors. The algorithms are intended for the computation of several functions as the division, square root, sines, cosines, exponential, logarithm, etc. By using redundant number representations and methods of Lyapunov stability for discrete dynamical systems, we obtain several algorithms (that can be glued together into an algorithm for parallel execution) having the same core and selection scheme in each iteration. We also prove their domains of convergence and discuss possible extensions. The last topic, also on appendix, studies the set of solutions of a class of nonlinear Fredholm integral equations with general delay. The delay is of functional character modelled by a continuous lag function. We ensure existence and uniqueness of a continuous (positive) solution of such equation. Moreover, under additional conditions, it is obtained the Fr´echet differentiability of the solution with respect to the lag function.
30
Kortelainen, T. (Tuomas). "On iteration-based security flaws in modern hash functions." Doctoral thesis, Oulun yliopisto, 2014. http://urn.fi/urn:isbn:9789526206431.
Full textAbstract:
Abstract The design principles proposed independently by both Ralph Merkle and Ivan Damgård in 1989 are applied widely in hash functions that are used in practice. The construction reads the message in one message block at a time and applies iteratively a compression function that, given a single message block and a hash value, outputs a new hash value. This iterative structure has some security weaknesses. It is vulnerable, for instance, to Joux's multicollision attack, herding attack that uses diamond structures and Trojan message attack. Our principal research topic comprises the deficiencies in hash function security induced by the Merkle-Damgård construction. In this work, we present a variant of Joux's multicollision attack. We also develop a new, time-saving algorithm for creating diamond structures. Moreover, two new efficient versions of Trojan message attack are introduced. The main contribution of the thesis is the analysis of generalized iterated hash functions. We study the combinatorial properties of words from a new perspective and develop results that are applied to give a new upper bound for the complexity of multicollision attacks against the so called q-bounded generalized iterated hash functionsTiivistelmä Vuonna 1989 Ralph Merkle ja Ivan Damgård ehdottivat toisistaan riippumatta hash-funktioille suunnitteluperiaatteita, joita käytetään tänä päivänä laajasti. Niin kutsuttu Merkle-Damgård -rakenne lukee viestin sisään viestiblokki kerrallaan ja käyttää tiivistefunktiota, joka liittää hash-arvoon ja viestiblokkiin uuden hash-arvon. Tällä iteratiivisella rakenteella on joitakin turvallisuusheikkouksia. Se on haavoittuva esimerkiksi Joux’n monitörmäyshyökkäykselle, timanttirakenteita hyödyntävälle paimennushyökkäykselle ja Troijan viesti -hyökkäykselle. Väitöskirjan pääasiallinen tutkimusaihe on Merkle-Damgård -rakenteen aiheuttamat puutteet tietoturvassa. Tässä työssä esitetään uusi versio Joux’n monitörmäyshyökkäyksestä, luodaan uusi aikaa säästävä algoritmi timanttirakenteiden kehittämiseksi ja kaksi uutta tehokasta versiota Troijan viesti -hyökkäyksestä. Väitöskirjan tärkein kontribuutio on yleistettyjen iteratiivisten hash-funktioiden turvallisuuden analysointi. Sanojen kombinatorisia ominaisuuksia tutkitaan uudesta näkökulmasta, jonka pohjalta kehitettyjä tuloksia soveltamalla luodaan uusi yläraja niin kutsuttujen q-rajoitettujen yleisten iteratiivisten hash-funktioiden monitörmäyshyökkäysten kompleksisuudelle
31
Schmidt, Ursula. "Motifs inévitables dans les mots." Paris 6, 1986. http://www.theses.fr/1986PA066303.
Full textAbstract:
Nous montrons que sur un alphabet a n lettres, il n'existe qu'un seul motif inévitable de longueur 2n-1, et que c'est une quasi-puissance. Par ailleurs, nous caractérisons complètement les motifs inévitables de longueur 2(n)-2 et 2(n)-3 ainsi que d'autres familles de motifs inévitables. Ensuite, nous calculons en temps linéaire l'ordre de quasi-puissance d'un mot ainsi que l'ordre de tous ses facteurs gauches. En utilisant le transducteur des suffixes, nous avons pu calculer en temps linéaire l'ordre de la plus grande pseudo-puissance qui est facteur d'un mot. Enfin, nous prouvons que tout motif à deux lettres de longueur supérieure ou égale à 13 est évitable sur un alphabet a deux lettres.
32
Liétard, Florian. "Évitabilité de puissances additives en combinatoire des mots." Electronic Thesis or Diss., Université de Lorraine, 2020. http://www.theses.fr/2020LORR0259.
Full textAbstract:
Ce document est principalement consacré à l'étude de l'évitabilité des cubes additifs dans les points fixes de morphismes. Les problèmes d'évitabilité des puissances additives sont connus pour avoir des implications dans la théorie des semi-groupes. Depuis un article publié en 2013 par J. Cassaigne, J.D. Currie, L. Schaeffer et J.O. Shallit, nous savons qu'il est possible de construire sur l'alphabet {0,1,3,4} un mot infini qui évite les cubes additifs, i.e., un mot qui ne contient pas trois facteurs consécutifs de même taille et même somme. Nous commençons par expliquer notre démarche de recherche avec cet article comme point de départ et par discuter des similarités entre les différents morphismes permettant d'éviter les cubes additifs sur des alphabets de 4 lettres. Nous expliciterons la façon dont nous avons programmé en C++ la recherche de morphismes créant des mots infinis sans puissances additives. Nous étendons ensuite la preuve de l'article de 2013 à un ensemble infini de morphismes (correspondant à une classe d'équivalence). Après l'étude d'un exemple nous développons une démonstration basée sur des substitutions entre les morphismes. Le résultat principal de ce document est qu'il est possible de donner, sur chaque alphabet de 4 lettres qui ne soit pas une transformation affine de {0,1,2,3}, un morphisme explicite possédant un point fixe infini sans cubes additifs. Ce travail, effectué en collaboration avec Matthieu Rosenfeld, a donné lieu à la publication d'un article. Pour démontrer ce résultat nous utilisons un argument contenu dans l'article de 2013, des majorations effectuées après disjonction des cas et des arguments de symétries entre les alphabets. Enfin, nous nous intéressons à l'évitabilité des cubes additifs sur {0,1,2,3} afin de tenter de répondre à une question posée en 2018 par M. Rao et M. Rosenfeld. Cet alphabet est le seul de quatre lettres pour lequel notre résultat principal n'apporte pas de réponse. Nous représentons graphiquement les mots possédant des puissances additives et nous développons deux programmes informatiques parallélisés. Le premier permet de détecter efficacement les puissances additives dans un mot très long, le second permet de créer un mot de plus de 70 millions de lettres sans cube additif sur {0,1,2,3}. Nous améliorons ainsi significativement la précédente borne connue (1.4x 10^5). Pour parvenir à ce résultat nous inversons périodiquement l'ordre de priorité pour le choix des lettres dans la construction du mot comme nous le suggéraient les représentations graphiques. Nos programmes utilisent des approches à la fois multi-ordinateurs et multi-threads pour gagner en efficacitéThe present thesis is dedicated to the various aspects of the problem of avoiding additive cubes in the fixed points of morphisms. Problems concerning the avoidability of additive powers are closely related to questions in the theory of semigroups. Since the publication of the article of J. Cassaigne, J.D. Currie, L. Schaeffer and J.O. Shallit (2013) we know that it is possible to construct an infinite word over {0, 1 ,3, 4} that avoids additive cubes, i.e., a word that avoids three consecutive blocks of same size and same sum. We first explain the methods used by the authors in their article, and then use it as a starting point for our discussions, with the ultimate aim to clarify the various similarities and connections between the different morphisms that allow to avoid additive cubes on alphabets over 4 letters. We next discuss our implementation in C++ of the investigation of theses morphisms, and then proceed to give an infinite family of morphisms (corresponding to classes of equivalence) that avoid additive cubes. After this investigation, we give a general proof scheme that is based on substitutions between morphisms. The main result of the thesis is that for any alphabet of 4 letters, with the sole exception of the alphabet {0, 1 ,2, 3} and its affine transformations, there is an explicit morphism whose infinite fixed point avoids additive cubes over the given alphabet. This work has been carried out in collaboration with Matthieu Rosenfeld and gave rise to an article in a peer-reviewed journal. In order to show this result, we use arguments from the article of Cassaigne et al., several numerical estimates for the underlying quantities, case disjunction as well as symmetry considerations for the alphabets under consideration. In the final part of the thesis we then study the question of avoiding additive cubes over {0, 1 ,2, 3} with the hope to answer a question posed by M. Rao and M. Rosenfeld in 2018. This alphabet is the only 4-letters alphabet where our result does not apply. We first study by graphical means the words that contain additive powers, and we discuss and implement in a second step two parallelized computer programs. The first program detects in an efficient way the occurrence of additive powers in very long words, whereas the second one allows to create long words over {0, 1 ,2, 3} without introducing any additive cube. With the help of these programs, we obtain a word of over 70 million letters that avoids additive cubes over {0, 1 ,2, 3}. This largely improves on the former known bound (1.4 x 10^5). To obtain our result, as suggested by our graphical considerations, we periodically reverse the order of priority for the choice of the letters in the construction of our word. Our programs use multi-computers and multi-threads settings to gain considerably on efficiency
33
Mammez, Cécile. "Deux exemples d'algèbres de Hopf d'extraction-contraction : mots tassés et diagrammes de dissection." Thesis, Littoral, 2017. http://www.theses.fr/2017DUNK0459/document.
Full textAbstract:
Ce manuscrit est consacré à l'étude de la combinatoire de deux algèbres de Hopf d'extraction-contraction. La première est l'algèbre de Hopf de mots tassés WMat introduite par Duchamp, Hoang-Nghia et Tanasa dont l'objectif était la construction d'un modèle de coproduit d'extraction-contraction pour les mots tassés. Nous expliquons certains sous-objets ou objets quotients ainsi que des applications vers d'autres algèbres de Hopf. Ainsi, nous considérons une algèbre de permutations dont le dual gradué possède un coproduit de déconcaténation par blocs et un produit de double battage décalé. Le double battage engendre la commutativité de l'algèbre qui est donc distincte de celle de Malvenuto et Reutenauer. Nous introduisons également une algèbre de Hopf engendrée par les mots tassés de la forme x₁...x₁. Elle est isomorphe à l'algèbre de Hopf des fonctions symétriques non commutatives. Son dual gradé est donc isomorphe à l'algèbre de Hopf des fonctions quasi-symétriques. Nous considérons également une algèbre de Hopf de compositions et donnons son interprétation en termes de coproduit semi-direct d'algèbres de Hopf. Le deuxième objet d'étude est l'algèbre de Hopf de diagrammes de dissection HD introduite par Dupont en théorie des nombres. Nous cherchons des éléments de réponse concernant la nature de sa cogèbre sous-jacente. Est-elle colibre ? La dimension des éléments primitifs de degré 3 ne permet pas de conclure. Le cas du degré 5 permet d'établir la non-coliberté dans le cas où le paramètre de HD vaut - 1. Nous étudions également la structure pré-Lie du dual gradué HD. Nous réduisons le champ de recherche à la sous-algèbre pré-Lie non triviale engendrée par le diagramme de dissection de degré 1. Cette algèbre pré-Lie n'est pas libreThis thesis deals with the study of combinatorics of two Hopf algebras. The first one is the packed words Hopf algebra WMAT introduced by Duchamp, Hoang-Nghia, and Tanasa who wanted to build a coalgebra model for packed words by using a selection-quotient process. We describe certain sub-objects or quotient objects as well as maps to other Hopf algebras. We consider first a Hopf algebra of permutations. Its graded dual has a block deconcatenation coproduct and double shuffle product. The double shuffle product is commutative so the Hopf algebra is different from the Malvenuto and Reutenauer one. We analyze then the Hopf algebra generated by packed words looking like x₁...x₁. This Hopf algebra and non commutative symmetric functions are isomorphic. So its graded dual and quasi-symmetric functions are isomorphic too. Finally we consider a Hopf algebra of compositions an give its interpretation in terms of a semi-direct coproduct structure. The second objet we study is the Hopf algebra of dissection diagrams HD introduced by Dupont in number theory. We study the cofreedom problem. We can't conclude with homogeneous primitive elements of degree 3. With the degree 5 case, we can say that is not cofree with the parameter -1. We study the pre-Lie algebra structure of HD's graded dual too. We consider in particular the sup-pre-Lie algebra generated by the dissection diagram of degree 1. It is not a free pre-Lie algebra
34
Mousavi, Haji Seyyed Hamoon. "Repetition in Words." Thesis, 2013. http://hdl.handle.net/10012/7737.
Full textAbstract:
The main topic of this thesis is combinatorics on words. The field of combinatorics on words dates back at least to the beginning of the 20th century when Axel Thue constructed an infinite squarefree sequence over a ternary alphabet. From this celebrated result also emerged the subfield of repetition in words which is the main focus of this thesis.
One basic tool in the study of repetition in words is the iteration of morphisms. In Chapter 1, we introduce this tool among other basic notions. In Chapter 2, we see applications of iterated morphisms in several examples. The second half of the chapter contains a survey of results concerning Dejean's conjecture. In Chapter 3, we generalize Dejean's conjecture to circular factors. We see several applications of iterated morphism in this chapter. We continue our study of repetition in words in Chapter 4, where we study the length of the shortest repetition-free word in regular languages. Finally, in Chapter 5, we conclude by presenting a number of open problems.
35
Rampersad, Narad. "Overlap-Free Words and Generalizations." Thesis, 2007. http://hdl.handle.net/10012/3421.
Full textAbstract:
The study of combinatorics on words dates back at least to the beginning of the 20th century and the work of Axel Thue. Thue was the first to give an example of an infinite word over a three letter alphabet that contains no squares (identical adjacent blocks) xx. This result was eventually used to solve some longstanding open problems in algebra and has remarkable connections to other areas of mathematics and computer science as well.
This thesis will consider several different generalizations of Thue's work. In particular we shall study the properties of infinite words avoiding various types of repetitions.
In Chapter 1 we introduce the theory of combinatorics on words. We present the basic definitions and give an historical survey of the area.
In Chapter 2 we consider the work of Thue in more detail. We present various well-known properties of the Thue-Morse word and give some generalizations. We examine Fife's characterization of the infinite overlap-free words and give a simpler proof of this result. We also present some applications to transcendental number theory, generalizing a classical result of Mahler.
In Chapter 3 we generalize a result of Seebold by showing that the only infinite 7/3-power-free binary words that can be obtained by iterating a morphism are the Thue-Morse word and its complement.
In Chapter 4 we continue our study of overlap-free and 7/3-power-free words. We discuss the squares that can appear as subwords of these words. We also show that it is possible to construct infinite 7/3-power-free binary words containing infinitely many overlaps.
In Chapter 5 we consider certain questions of language theory. In particular, we examine the context-freeness of the set of words containing overlaps. We show that over a three-letter alphabet, this set is not context-free, and over a two-letter alphabet, we show that this set cannot be unambiguously context-free.
In Chapter 6 we construct infinite words over a four-letter alphabet that avoid squares in any arithmetic progression of odd difference. Our constructions are based on properties of the paperfolding words. We use these infinite words to construct non-repetitive tilings of the integer lattice.
In Chapter 7 we consider approximate squares rather than squares. We give constructions of infinite words that avoid such approximate squares.
In Chapter 8 we conclude the work and present some open problems.
36
Glen, Amy Louise. "On Sturmian and Episturmian words, and related topics." 2006. http://hdl.handle.net/2440/37765.
Full textAbstract:
In recent years, combinatorial properties of finite and infinite words have become increasingly important in fields of physics, biology, mathematics, and computer science. In particular, the fascinating family of Sturmian words has become an extremely active subject of research. These infinite binary sequences have numerous applications in various fields of mathematics, such as symbolic dynamics, the study of continued fraction expansion, and also in some domains of physics ( quasicrystal modelling ) and computer science ( pattern recognition, digital straightness ). There has also been a recent surge of interest in a natural generalization of Sturmian words to more than two letters - the so - called episturmian words, which include the well - known Arnoux - Rauzy sequences. This thesis represents a significant contribution to the study of Sturmian and episturmian words, and related objects such as generalized Thue - Morse words and substitutions on a finite alphabet. Specifically, we prove some new properties of certain palindromic factors of the infinite Fibonacci word; establish generalized ' singular ' decompositions of suffixes of certain morphic Sturmian words; completely describe where palindromes occur in characteristic Sturmian words; explicitly determine all integer powers occurring in a certain class of k-strict episturmian words ( including the k-bonacci word ) ; and prove that certain episturmian and generalized Thue - Morse continued fractions are transcendental. Lastly, we begin working towards a proof of a characterization of invertible substitutions on a finite alphabet, which generalizes the fact that invertible substitutions on two letters are exactly the Sturmian morphisms.Thesis (Ph.D.)--School of Mathematical Sciences, 2006.
37
Schaeffer, Luke. "Deciding Properties of Automatic Sequences." Thesis, 2013. http://hdl.handle.net/10012/7899.
Full textAbstract:
In this thesis, we show that several natural questions about automatic sequences can be expressed as logical predicates and then decided mechanically. We extend known results in this area to broader classes of sequences (e.g., paperfolding words), introduce new operations that extend the space of possible queries, and show how to process the results.
We begin with the fundamental concepts and problems related to automatic sequences, and the corresponding numeration systems. Building on that foundation, we discuss the general logical framework that formalizes the questions we can mechanically answer. We start with a first-order logical theory, and then extend it with additional predicates and operations. Then we explain a slightly different technique that works on a monadic second- order theory, but show that it is ultimately subsumed by an extension of the first-order theory.
Next, we give two applications: critical exponent and paperfolding words. In the critical exponent example, we mechanically construct an automaton that describes a set of rational numbers related to a given automatic sequence. Then we give a polynomial-time algorithm to compute the supremum of this rational set, allowing us to compute the critical exponent and many similar quantities. In the paperfolding example, we extend our mechanical procedure to the paperfolding words, an uncountably infinite collection of infinite words.
In the following chapter, we address abelian and additive problems on automatic sequences. We give an example of a natural predicate which is provably inexpressible in our first-order theory, and discuss alternate methods for solving abelian and additive problems on automatic sequences.
We close with a chapter of open problems, drawn from the earlier chapters.
38
Goc, Daniel. "Automatic Sequences and Decidable Properties: Implementation and Applications." Thesis, 2013. http://hdl.handle.net/10012/7884.
Full textAbstract:
In 1912 Axel Thue sparked the study of combinatorics on words when he showed that the Thue-Morse sequence contains no overlaps, that is, factors of the form ayaya.
Since then many interesting properties of sequences began to be discovered and studied.
In this thesis, we consider a class of infinite sequences generated by automata, called the k-automatic sequences. In particular, we present a logical theory in which many properties of k-automatic sequences can be expressed as predicates and we show that such predicates are decidable.
Our main contribution is the implementation of a theorem prover capable of practically characterizing many commonly sought-after properties of k-automatic sequences. We showcase a panoply of results achieved using our method. We give new explicit descriptions of the recurrence and appearance functions of a list of well-known k-automatic sequences. We define a related function, called the condensation function, and give explicit descriptions for it as well. We re-affirm known results on the critical exponent of some sequences and determine it for others where it was previously unknown. On the more theoretical side, we show that the subword complexity p(n) of k-automatic sequences is k-synchronized, i.e., the language of pairs (n, p(n)) (expressed in base k) is accepted by an automaton. Furthermore, we prove that the Lyndon factorization of k-automatic sequences is also k-automatic and explicitly compute the factorization for several sequences. Finally, we show that while the number of unbordered factors of length n is not k-synchronized, it is k-regular.
39
(9518483), Yucong Zhang. "Combinatorial methods for counting pattern occurrences in a Markovian text." Thesis, 2020.
Find full textAbstract:
In this dissertation, we provide combinatorial methods to obtain the probabilistic mul-tivariate generating function that counts the occurrences of patterns in a text generated by a Markovian source. The generating function can then be expanded into the Taylor series in which the power of a term gives the size of a text and the coeÿcient provides the proba-bilities of all possible pattern occurrences with the text size. The analysis is on the basis of the inclusion-exclusion principle to pattern counting (Goulden and Jackson, 1979 and 1983) and its application that Bassino et al. (2012) used for obtaining the generating function in the context of the Bernoulli text source. We followed the notations and concepts created by Bassino et al. in the discussion of distinguished patterns and non-reduced pattern sets, with modifications to the Markovian dependence. Our result is derived in the form of a linear matrix equation in which the number of linear equations depends on the size of the alphabet. In addition, we compute the moments of pattern occurrences and discuss the impact of a Markovian text to the moments comparing to the Bernoulli case. The methodology that we use involves the inclusion-exclusion principle, stochastic recurrences, and combinatorics on words including probabilistic multivariate generating functions and moment generating functions.
40
ROSONE, Giovanna. "Balancing and clustering of words: a combinatorial analysis of the Burrows & Wheeler Transform." Doctoral thesis, 2010. http://hdl.handle.net/10447/97515.
Full textAbstract:
The Burrows-Wheeler Transform (denoted by BWT) is a well founded mathematical transformation on sequences introduced in 1994, widely used in the context of Data Compression and recently studied also from a combinatorial point of view. The transformation does not itself compress the data, but it produces a permutation bwt(w) of an input string w that is easier to compress than the original one, with some fast locally-adaptive algorithms, such as Move-to-Front in combination with Huffman or arithmetic coding. It is well-known that in most real texts, characters with the same or similar contexts tend to be the same. So, the BWT tends to group together characters which occur adjacent to similar text substring and this property is good for compression.
The aim of this thesis is to study such “clustering effect” by using notions and methods from Combinatorics on Words.
The notion of balance of a word plays a central role in our investigation. Empirical observations suggest that balance is actually the combinatorial property of input word that ensure optimal BWT compression. Moreover, it is reasonable to assume that the more balanced the input word is, the more local similarity one has after BWT (and therefore the better the compression is). This hypothesis is here corroborate by experiments on “real” text, by using local entropy as a measure of the degree of balance of a word.
In the setting of Combinatorics on Words, a sound confirmation of previous hypothesis is given by a result in [Mantaci, Restivo, and Sciortino: Burrows Wheeler transform and Sturmian words. Inf. Process. Lett. 86(5): 241-246 (2003)], which states that, in the case of a binary alphabet, there is an equivalence between circularly balanced words, words having a clusterized BWT, and the conjugates of standard words. In the case of alphabet of size greater than two, there is no more equivalence. So we investigate the relationships between these notions, and other related ones (as, for instance, palindromic richness) in the case of a general alphabet.
41
Sýkora, Jiří. "Kombinatorika hashovacích funkcí." Master's thesis, 2012. http://www.nusl.cz/ntk/nusl-304496.
Full textAbstract:
In this thesis, we study hash functions. We focus mainly on the famous Merkle-Damg˚ard construction and its generalisation. We show that even this generalised construction is not resistant to multicollision attacks. Combinatorics on words plays a fundamental role in the construction of our attack. We prove that regularities unavoidably appear in long words with bounded number of symbol occurences. We present our original results concerning regularities in long words. We lower some earlier published estimates, thus reducing the comlexity of the attack. Our results show that generalised iterated hash functions are interesting rather from the theoretical than practical point of view. 1
42
Hadravová, Jana. "Struktura ekvivalenčních množin." Doctoral thesis, 2015. http://www.nusl.cz/ntk/nusl-333779.
Full textAbstract:
Title: Structure of equality sets Author: Jana Hadravová Department: Department of Algebra Supervisor: doc. Mgr. Štěpán Holub, Ph.D., Dept. of Algebra Abstract: Binary equality set of two morphisms g, h : ⌃⇤ ! A⇤ is a set of all words w over two-letter alphabet ⌃ satisfying g(w) = h(w). Elements of this set are called binary equality words. One of the important results of research on binary equality sets is the proof of the fact that each binary equality set is generated by at most two words provided that both morphisms g and h are non-periodic. Moreover, if a binary equality set is generated by exactly two words, then the structure of both generators, and therefore of the whole set, is uniquely given. This work presents the results of our research on the structure of binary equality sets with a single generator. Importantly, these generators can be decomposed into simpler structures. Generators which can not be further decomposed are called simple equality words. First part of the presented work describes the structure of simple equality words and introduces their detailed classification. The main result of the first part is a precise characterisation of su ciently large simple equality words. In the second part, the work describes the iterative process which transforms a general generator of a binary...
43
Xu, Zhi. "The Frobenius Problem in a Free Monoid." Thesis, 2009. http://hdl.handle.net/10012/4574.
Full textAbstract:
Given positive integers c1,c2,...,ck with gcd(c1,c2,...,ck) = 1, the Frobenius problem (FP) is to compute the largest integer g(c1,c2,...,ck) that cannot be written as a non-negative integer linear combination of c1,c2,...,ck. The Frobenius problem in a free monoid (FPFM) is a non-commutative generalization of the Frobenius problem. Given words x1,x2,...,xk such that there are only finitely many words that cannot be written as concatenations of words in {x1,x2,...,xk}, the FPFM is to find the longest such words. Unlike the FP, where the upper bound g(c1,c2,...,ck)≤max 1≤i≤k ci2 is quadratic, the upper bound on the length of the longest words in the FPFM can be exponential in certain measures and some of the exponential upper bounds are tight. For the 2FPFM, where the given words over Σ are of only two distinct lengths m and n with 1
44
Williams, Aaron Michael. "Shift gray codes." Thesis, 2009. http://hdl.handle.net/1828/1966.
Full textAbstract:
Combinatorial objects can be represented by strings, such as 21534 for the permutation (1 2) (3 5 4), or 110100 for the binary tree corresponding to the balanced parentheses (()()). Given a string s = s1 s2 sn, the right-shift operation shift(s, i, j) replaces the substring si si+1..sj by si+1..sj si. In other words, si is right-shifted into position j by applying the permutation (j j−1 .. i) to the indices of s. Right-shifts include prefix-shifts (i = 1) and adjacent-transpositions (j = i+1). A fixed-content language is a set of strings that contain the same multiset of symbols. Given a fixed-content language, a shift Gray code is a list of its strings where consecutive strings differ by a shift. This thesis asks if shift Gray codes exist for a variety of combinatorial objects. This abstract question leads to a number of practical answers.
The first prefix-shift Gray code for multiset permutations is discovered, and it provides the first algorithm for generating multiset permutations in O(1)-time while using O(1) additional variables. Applications of these results include more efficient exhaustive solutions to stacker-crane problems, which are natural NP-complete traveling salesman variants. This thesis also produces the fastest algorithm for generating balanced parentheses in an array, and the first minimal-change order for fixed-content necklaces and Lyndon words.
These results are consequences of the following theorem: Every bubble language has a right-shift Gray code. Bubble languages are fixed-content languages that are closed under certain adjacent-transpositions. These languages generalize classic combinatorial objects: k-ary trees, ordered trees with fixed branching sequences, unit interval graphs, restricted Schr oder and Motzkin paths, linear-extensions of B-posets, and their unions, intersections, and quotients. Each Gray code is circular and is obtained from a new variation of lexicographic order known as cool-lex order.
Gray codes using only shift(s, 1, n) and shift(s, 1, n−1) are also found for multiset permutations. A universal cycle that omits the last (redundant) symbol from each permutation is obtained by recording the first symbol of each permutation in this Gray code. As a special case, these shorthand universal cycles provide a new fixed-density analogue to de Bruijn cycles, and the first universal cycle for the "middle levels" (binary strings of length 2k + 1 with sum k or k + 1).
45
Rebenich, Niko. "Counting prime polynomials and measuring complexity and similarity of information." Thesis, 2016. http://hdl.handle.net/1828/7251.
Full textAbstract:
This dissertation explores an analogue of the prime number theorem for polynomials over finite fields as well as its connection to the necklace factorization algorithm T-transform and the string complexity measure T-complexity. Specifically, a precise asymptotic expansion for the prime polynomial counting function is derived. The approximation given is more accurate than previous results in the literature while requiring very little computational effort. In this context asymptotic series expansions for Lerch transcendent, Eulerian polynomials, truncated polylogarithm, and polylogarithms of negative integer order are also provided. The expansion formulas developed are general and have applications in numerous areas other than the enumeration of prime polynomials.
A bijection between the equivalence classes of aperiodic necklaces and monic prime polynomials is utilized to derive an asymptotic bound on the maximal T-complexity value of a string. Furthermore, the statistical behaviour of uniform random sequences that are factored via the T-transform are investigated, and an accurate probabilistic model for short necklace factors is presented.
Finally, a T-complexity based conditional string complexity measure is proposed and used to define the normalized T-complexity distance that measures similarity between strings. The T-complexity distance is proven to not be a metric. However, the measure can be computed in linear time and space making it a suitable choice for large data sets.Graduate
0544 0984 0405
nrebenich@gmail.com
46
Sauer, Paul Van der Merwe. "The complexity of unavoidable word patterns." Thesis, 2019. http://hdl.handle.net/10500/27343.
Full textAbstract:
Bibliography: pages 192-195The avoidability, or unavoidability of patterns in words over finite alphabets has been studied extensively. The word α over a finite set A is said to be unavoidable for an infinite set B+ of nonempty words over a finite set B if, for all but finitely many elements w of B+, there exists a semigroup morphism φ ∶ A+ → B+ such that φ(α) is a factor of w. In this treatise, we start by presenting a historical background of results that are related to unavoidability. We present and discuss the most important theorems surrounding unavoidability in detail. We present various complexity-related properties of unavoidable words. For words that are unavoidable, we provide a constructive upper bound to the lengths of words that avoid them. In particular, for a pattern α of length n over an alphabet of size r, we give a concrete function N(n, r) such that no word of length N(n, r) over the alphabet of size r avoids α. A natural subsequent question is how many unavoidable words there are. We show that the fraction of words that are unavoidable drops exponentially fast in the length of the word. This allows us to calculate an upper bound on the number of unavoidable patterns for any given finite alphabet. Subsequently, we investigate computational aspects of unavoidable words. In particular, we exhibit concrete algorithms for determining whether a word is unavoidable. We also prove results on the computational complexity of the problem of determining whether a given word is unavoidable. Specifically, the NP-completeness of the aforementioned problem is established.
Decision Sciences
D. Phil. (Operations Research)