Repetitions in words
No Thumbnail Available
Date
2024
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Repetitions are fundamental properties of words, and different types of repetitions have been explored in the area of word combinatorics. This thesis investigates two types of repetitions: squares and antisquares. We investigate the square conjecture that anticipates the number of distinct squares in a word is less than its length. It is known that any location of a word can be mapped to at most two rightmost squares, and a pair of these squares was referred to as an FS-double square. For simplicity, we will refer to the longer square in this pair as an FS-double square throughout this thesis. We examine the properties of words containing FS-double squares and explore the consecutive locations starting with FS-double squares. We observe that FS-double squares introduce no-gain locations where no rightmost squares ocCur. The count of these no-gain locations in words with a sequence of FS-double squares demonstrates that the square density of such words is less than 11/6. Furthermore, we investigate words that possess FS-double squares and maintain an equivalent number of such squares when reversed. We prove that the maximum number of FS-double squares in such a word is less than 1/11 th of the length of the word. Another aspect of our research involves counting squares in a repetition. A non-primitive word has a tom u for some non-empty word u and some positive integer k such that ko2. With no-gain locations and FS-double squares in these words, we conclude that the square density of such words approaches 1/2 as k increases. Also, we work on the lower bound of the square conjecture. The previous lower bound is obtained using a structure that generates words containing a high number of
distinct squares. We identify simiiar structures but produce words with more distinct squares. We also study antisquare, a special repetition of the form uiw here u is a binary word, and üis its complement. We show that a Word w can contain at most w((w|+2)/8 antisquares, and the lower bound for the number of distinct antisauares in w is lw-1.
Description
Supervisors: Kapoor, Kalpesh and Kenkireth, Benny George
Keywords
COMPUTER SCIENCE AND ENGINEERING