Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 38 for “"Combinatorics on Words"”.
-
Periodicity and Repetition in Combinatorics on Words
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 …
-
DNA Computing: Modelling in Formal Languages and Combinatorics on Words, and Complexity Estimation
DNA computing, an essential area of unconventional computing research, encodes problems using DNA molecules and solves them using biological processes. This thesis contributes to the theoretical research in DNA computing by modelling biological processes as computations and by studying formal …
-
Contributions to combinatorics on words in an abelian context and covering problems in graphs
This thesis 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 …
-
Systèmes de numération abstraits et combinatoire des mots (habilitation à diriger des recherches)
… summary the main properties of abstract numeration systems and their links to combinatorics on words and combinatorial game theory.
-
Repetition in Words
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 …
-
Powers and Anti-Powers in Binary Words
Fici et al. recently introduced the notion of anti-powers in the context of combinatorics on words. A power (also called tandem repeat) is a sequence of consecutive identical blocks. An anti-power is a sequence of consecutive distinct blocks of the same length. Fici et al. showed that the existence …
-
On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words
How to reconstruct a word from a given set ofscattered factors? How to determine thelocalityof a word? Or how to determine theprefix normal words recursively? Combinatorics on words, even though this domain is relatively young, has by now a lot of subdomains, which all seek to deter-mine the …
-
On the Properties and Structure of Bordered Words and Generalizations
Combinatorics on words is a field of mathematics and theoretical computer science that is concerned with sequences of symbols called words, or strings. One class of words that are ubiquitous in combinatorics on words, and theoretical computer science more broadly, are the bordered words. The word w …
-
Infinite Sequences and Pattern Avoidance
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 …
-
Theoretical and Practical Aspects Related to the Avoidability of Patterns in Words
Studying avoidability of patterns has long-established roots and has been performed by renowned scholars. Studies of this nature can be traced back over one hundred years. This thesis concerns repetitive structures in words. More precisely, it contributes to studying appearance and absence of such …
-
Convex Geometry of Subword Complexes of Coxeter Groups
This monography presents results related to the convex geometry of a family of simplicial complexes called ``subword complexes''. These simplicial complexes are defined using the Bruhat order of Coxeter groups. Despite a simple combinatorial definition much of their combinatorial properties are …
-
Overlap-Free Words and Generalizations
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 …
-
New Methods for Analyzing the Properties of Automatic Sequences
Automatic sequences and morphic words lie at the intersection of automata theory, logic, and combinatorics on words. Many of their structural properties can be formulated as logical predicates over integer representations and decided using automata. This thesis presents automata-based methods for …
-
Decision Algorithms for Ostrowski-Automatic Sequences
We extend the notion of automatic sequences to a broader class, the Ostrowski-automatic sequences. We develop a procedure for computationally deciding certain combinatorial and enumeration questions about such sequences that can be expressed as predicates in first-order logic. In Chapter 1, we …
-
Novel Structural Properties and An Improved Bound for the Number Distinct Squares in a Strings
Combinatorics on words explore words – often called strings in the com- puter science community, or monoids in mathematics – and their structural properties. One of the most studied question deals with repetitions which are a form of redundancy. The thesis focuses on estimating the maximum number …
-
Theoretical and Practical Aspects Related to the Avoidability of Patterns in Words
This thesis concerns repetitive structures in words. More precisely, it contributes to studying appearance and absence of such repetitions in words. In the first and major part of this thesis, we study avoidability of unary patterns with permutations. The second part of this thesis deals with …
-
A Generalization of Square-free Strings
… is in the general area of String Algorithms and Combinatorics on Words. Specifically, we study a generalization of square-free strings, shuffle properties of strings, and formalizing the reasoning about finite strings. The existence of infinitely long square-free strings (strings with no adjacent …
-
Automatic Sequences and Decidable Properties: Implementation and Applications
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 …
-
Properties of Two-Dimensional Words
Combinatorics on words in one dimension is a well-studied subfield of theoretical computer science with its origins in the early 20th century. However, the closely-related study of two-dimensional words is not as popular, even though many results seem naturally extendable from the one-dimensional …
-
Avoiding and Enforcing Repetitive Structures in Words
The focus of this thesis is on the study of repetitive structures in words, a central topic in the area of combinatorics on words. The results presented in the thesis at hand are meant to extend and enrich the existing theory concerning the appearance and absence of such structures. In the first …
Page 1 of 2