Please note: This PhD seminar will take place online.
Zihao Wang, PhD candidate
David R. Cheriton School of Computer Science
Supervisor: Professor Lila Kari
As part of ongoing efforts to view biological processes as computations, several formal models of DNA-based processes have been proposed and studied in the formal language literature. A new word operation inspired by a DNA recombination lab protocol called Cross-pairing Polymerase Chain Reaction (XPCR) and its variations were proposed. More precisely, the word operation called word blending models a special case of XPCR, where two words xwu and vwy sharing a non-empty overlap part w generate the word xwy. This phenomenon was also found in linguistics under the name portmanteau (e.g., smoke + fog = smog). The word operation called conjugate word blending is a more restricted version of word blending, where u and v are required to be the same non-empty word. We studied the closure properties of the Chomsky families of languages under these operations, the iterated version of word blending, the existence of a solution to equations involving this operation, and its state complexity.