Nondeterministic State Complexity of Site-Directed Operations

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

Recommended citation: Oliver Lyon, Kai Salomma, "Nondeterministic State Complexity of Site-Directed Operations." Queen"s University, 2021.