Relevant bibliographies by topics / Combinatorics on words / Dissertations / Theses
To see the other types of publications on this topic, follow the link: Combinatorics on words.

Dissertations / Theses on the topic 'Combinatorics on words'

Author: Grafiati
Published: 4 June 2021
Last updated: 25 July 2025

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

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 text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
2

Wang, Ming-wei. "Periodicity and Repetition in Combinatorics on Words." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1136.

Full text
Abstract:
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 (DL
APA, Harvard, Vancouver, ISO, and other styles
3

Klouda, karel. "Non-standard numeration systemes and combinatorics on words." Paris 7, 2010. http://www.theses.fr/2010PA077161.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 result
APA, Harvard, Vancouver, ISO, and other styles
5

Rampersad, Narad. "Infinite Sequences and Pattern Avoidance." Thesis, University of Waterloo, 2004. http://hdl.handle.net/10012/1155.

Full text
Abstract:
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) <i>xx</i>. 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 c
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 mon
APA, Harvard, Vancouver, ISO, and other styles
7

Rosenfeld, Matthieu. "Avoidability of Abelian Repetitions in Words." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSEN033/document.

Full text
Abstract:
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 e
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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&nbsp;&nbsp; jPal(w)j, where jPal(w)j denotes the number of palindromic factors of w. We study innite words, to which this de&nbsp; nition can be naturally extended. There are many results in the literature about the so- called rich words (words&nbsp; of defect 0), while words of nite positive defect have been studied signicantly less; for some time (until recently) it was not known whether
APA, Harvard, Vancouver, ISO, and other styles
9

Nevisi, Hossein. "Conditions on the existence of unambiguous morphisms." Thesis, Loughborough University, 2012. https://dspace.lboro.ac.uk/2134/10282.

Full text
Abstract:
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 unambig
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 con
APA, Harvard, Vancouver, ISO, and other styles
12

Dolce, Francesco. "Codes bifixes, combinatoire des mots et systèmes dynamiques symboliques." Thesis, Paris Est, 2016. http://www.theses.fr/2016PESC1036/document.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 entr
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 da
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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, ap
APA, Harvard, Vancouver, ISO, and other styles
16

Heuer, Manuela. "Combinatorial aspects of root lattices and words." Thesis, Open University, 2010. http://oro.open.ac.uk/24046/.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 f
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 suite
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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-
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
23

Burns, Jonathan. "Recursive Methods in Number Theory, Combinatorial Graph Theory, and Probability." Scholar Commons, 2014. https://scholarcommons.usf.edu/etd/5193.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 fo
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
27

Wojcik, Caius. "Factorisations des mots de basse complexité." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1340.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
Doutoramento em Matemática<br>Nesta 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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 deficienci
APA, Harvard, Vancouver, ISO, and other styles
31

Schmidt, Ursula. "Motifs inévitables dans les mots." Paris 6, 1986. http://www.theses.fr/1986PA066303.

Full text
Abstract:
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 mot
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 rech
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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 dou
APA, Harvard, Vancouver, ISO, and other styles
34

Mousavi, Haji Seyyed Hamoon. "Repetition in Words." Thesis, 2013. http://hdl.handle.net/10012/7737.

Full text
Abstract:
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 c
APA, Harvard, Vancouver, ISO, and other styles
35

Rampersad, Narad. "Overlap-Free Words and Generalizations." Thesis, 2007. http://hdl.handle.net/10012/3421.

Full text
Abstract:
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 type
APA, Harvard, Vancouver, ISO, and other styles
36

Glen, Amy Louise. "On Sturmian and Episturmian words, and related topics." 2006. http://hdl.handle.net/2440/37765.

Full text
Abstract:
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 rece
APA, Harvard, Vancouver, ISO, and other styles
37

Schaeffer, Luke. "Deciding Properties of Automatic Sequences." Thesis, 2013. http://hdl.handle.net/10012/7899.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
38

Goc, Daniel. "Automatic Sequences and Decidable Properties: Implementation and Applications." Thesis, 2013. http://hdl.handle.net/10012/7884.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
39

(9518483), Yucong Zhang. "Combinatorial methods for counting pattern occurrences in a Markovian text." Thesis, 2020.

Find full text
Abstract:
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 f
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
41

Sýkora, Jiří. "Kombinatorika hashovacích funkcí." Master's thesis, 2012. http://www.nusl.cz/ntk/nusl-304496.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
42

Hadravová, Jana. "Struktura ekvivalenčních množin." Doctoral thesis, 2015. http://www.nusl.cz/ntk/nusl-333779.

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
43

Xu, Zhi. "The Frobenius Problem in a Free Monoid." Thesis, 2009. http://hdl.handle.net/10012/4574.

Full text
Abstract:
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, t
APA, Harvard, Vancouver, ISO, and other styles
44

Williams, Aaron Michael. "Shift gray codes." Thesis, 2009. http://hdl.handle.net/1828/1966.

Full text
Abstract:
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 f
APA, Harvard, Vancouver, ISO, and other styles
45

Rebenich, Niko. "Counting prime polynomials and measuring complexity and similarity of information." Thesis, 2016. http://hdl.handle.net/1828/7251.

Full text
Abstract:
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 neg
APA, Harvard, Vancouver, ISO, and other styles
46

Sauer, Paul Van der Merwe. "The complexity of unavoidable word patterns." Thesis, 2019. http://hdl.handle.net/10500/27343.

Full text
Abstract:
Bibliography: pages 192-195<br>The 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 pre
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the bibliographies on the topic 'Combinatorics on words' for other source types:
Journal articles Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography