Western University Computer ScienceWestern Science

MSc Thesis Defense


Zihao Wang

Word Blending and Other Formal Models of Bio-operations


Thesis Examiners:

Tuesday, May 29, 2018
130 a.m.
Middlesex College, Room 320
Dr. Lila Kari
Dr. Marc Moreno Maza
Dr. Roberto Solis Oba

Dr. David Jeffrey (Applied Math)
Dr. Robert Webber



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. In this thesis, we survey some classical formal language word and language operations, as well as several bio-operations, and we propose a new operation inspired by a DNA recombination lab protocol known as Cross- pairing Polymerase Chain Reaction, or XPCR. More precisely, we define and study a word operation called word blending which models a special case of XPCR, where two words xwu and vwy sharing a non-empty overlap part w generate the word xwy. Properties of word blending that we study include closure properties of the Chomsky families of languages under this operation and its iterated version, existence of solution to equations involving this operation, and its state complexity.