Nondeterministic State Complexity of Site-Directed Operations

Thumbnail Image
Lyon, Oliver
Automata Theory , Regular Languages , Formal Languages , Descriptional Complexity , Nondeterministic Finite Automata
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.
External DOI