Study of primitive and pseudo-bordered partial words
No Thumbnail Available
Date
2019
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The area of Combinatorics on words is a theoretical development of Discrete Mathematics and Theoretical Computer Science. It has numerous application across several areas including the field of coding theory, formal language theory, semigroup theory, dynamical system. A word is a sequence of letters from a given alphabet. A partial word is a canonical extension of a word that may have some unknown symbols known as “do not know” symbols or “holes”. Study of partial word was motivated by its practical application in Molecular Biology such as comparison of two genes. Alignment of two DNA sequences can be viewed as construction of two partial words that are compatible. A partial word is said to be primitive if it is not contained in some power of a word. Many important properties on partial words such as conjugacy and commutativity, Periodicity theorem of Fine and Wilf and Critical factorization theorem have been investigated. This thesis presents a theoretical investigation on primitive partial words and pseudo-bordered partial words.In our first work, we explore the position of the language of primitive partial words in the conventional Chomsky hierarchy. We present an indexed grammar for the set of nonprimitive words. In our second work, we consider several point mutation operations on primitive partial words that preserves primitivity. We consider deletion of a symbol, insertion of a symbol, exchange of two distinct consecutive symbols and substitute a symbol by another symbol from the underlying alphabet. In our third work, we consider a variation of bordered partial words known as pseudo-bordered partial words for various pseudo-identity functions. We explore several combinatorial properties of Θ-(un)bordered partial words such as disjunctivity of Θ-unborderd partial words, characterization of Θ-bordered partial words and several language classes in connection with Θ-(un)bordered partial words. We also introduce Θ-primitive partial words and investigate the problem of Θ-conjugacy and Θ-commutativity. In our final work, we study the notion of palindromes and pseudo-palindromes in partial words and explore several combinatorial properties.
Description
Supervisor: Kalpesh Kapoor
Keywords
MATHEMATICS