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"”.

  1. 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 …

    waterloo Repository record for Periodicity and Repetition in Combinatorics on Words (opens in a new tab)

  2. 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 …

    waterloo Repository record for DNA Computing: Modelling in Formal Languages and Combinatorics on Words, and Complexity Estimation (opens in a new tab)

  3. 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 …

    liege Repository record for Contributions to combinatorics on words in an abelian context and covering problems in graphs (opens in a new tab) Download PDF for Contributions to combinatorics on words in an abelian context and covering problems in graphs (opens in a new tab)

  4. 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.

    liege Repository record for Systèmes de numération abstraits et combinatoire des mots (habilitation à diriger des recherches) (opens in a new tab) Restricted access

  5. 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 …

    waterloo Repository record for Repetition in Words (opens in a new tab)

  6. 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 …

    waterloo Repository record for Powers and Anti-Powers in Binary Words (opens in a new tab)

  7. 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 …

    cau-kiel Repository record for On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words (opens in a new tab)

  8. 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 …

    waterloo Repository record for On the Properties and Structure of Bordered Words and Generalizations (opens in a new tab)

  9. 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 …

    waterloo Repository record for Infinite Sequences and Pattern Avoidance (opens in a new tab)

  10. 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 …

    cau-kiel Repository record for Theoretical and Practical Aspects Related to the Avoidability of Patterns in Words (opens in a new tab)

  11. 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 …

    fu-berlin Repository record for Convex Geometry of Subword Complexes of Coxeter Groups (opens in a new tab)

  12. 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 …

    waterloo Repository record for Overlap-Free Words and Generalizations (opens in a new tab)

  13. 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 …

    waterloo Repository record for New Methods for Analyzing the Properties of Automatic Sequences (opens in a new tab)

  14. 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 …

    waterloo Repository record for Decision Algorithms for Ostrowski-Automatic Sequences (opens in a new tab)

  15. 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 …

    mcmaster Repository record for Novel Structural Properties and An Improved Bound for the Number Distinct Squares in a Strings (opens in a new tab)

  16. 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 …

    cau-kiel Repository record for Theoretical and Practical Aspects Related to the Avoidability of Patterns in Words (opens in a new tab)

  17. 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 …

    mcmaster Repository record for A Generalization of Square-free Strings (opens in a new tab)

  18. 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 …

    waterloo Repository record for Automatic Sequences and Decidable Properties: Implementation and Applications (opens in a new tab)

  19. 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 …

    waterloo Repository record for Properties of Two-Dimensional Words (opens in a new tab)

  20. 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 …

    cau-kiel Repository record for Avoiding and Enforcing Repetitive Structures in Words (opens in a new tab)

Page 1 of 2