Nondeterministic State Complexity of Site-Directed Operations
Loading...
Authors
Lyon, Oliver
Date
Type
thesis
Language
eng
Keyword
Automata Theory , Regular Languages , Formal Languages , Descriptional Complexity , Nondeterministic Finite Automata
Alternative Title
Abstract
In this thesis, we consider the nondeterministic state complexity of PCR-inspired (polymerase chain reaction) operations. Site-directed operations are used to formally describe the behavior of certain DNA (deoxyribonucleic acid) editing methods which need to identify a subsequence in a host DNA strand prior to editing. These operations can be considered as language operations acting to match patterns between two sets of strings.
The site-directed insertion and deletion operations, insert or delete into a host string based on a directing string. The directing string must have a non-empty outfix that matches a substring in the host before operating. Prefix and suffix directed insertion are similar to site-directed insertion except, instead of matching a non-empty outfix, a non-empty prefix or suffix is matched before insertion. We consider the nondeterministic state complexity of site-directed insertion and deletion. Constructing a nondeterministic finite automaton (NFA) for the operation provides an upper bound for the state complexity of the operation. Our construction improves the earlier upper bound in the literature. Existing literature did not give lower bounds for the nondeterministic state complexity of site-directed insertion and deletion. Using the fooling set method we establish lower bounds that are fairly close to the upper bound, albeit the lower bound is not tight.
The other operations considered are those that identify subsets of a language. The prefix, suffix, infix and outfix operations check to see if a word from another language is contained as a prefix, suffix, infix or outfix of the target word. We introduce NFA constructions which apply these operations over regular languages, and establish bounds for the prefix, suffix, infix and outfix operations.
Description
Citation
Publisher
License
Queen's University's Thesis/Dissertation Non-Exclusive License for Deposit to QSpace and Library and Archives Canada
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution-NonCommercial-NoDerivs 3.0 United States
ProQuest PhD and Master's Theses International Dissemination Agreement
Intellectual Property Guidelines at Queen's University
Copying and Preserving Your Thesis
This publication is made available by the authority of the copyright owner solely for the purpose of private study and research and may not be copied or reproduced except as permitted by the copyright laws without written authority from the copyright owner.
Attribution-NonCommercial-NoDerivs 3.0 United States