Correspondence:
[†]
Address for correspondence: School of Computer Science, University of Waterloo, Canada
Note: [*] This research was supported by the NSERC (Natural Sciences and Engineering Research Council of Canada) Discovery Grant R2824A01, and a University of Waterloo School of Computer Science Grant to L.K.
Abstract: In this paper we define and investigate a binary word operation that formalizes an experimentally observed outcome of DNA computations, performed to generate a small gene library, and implemented using a DNA recombination technique called Cross-pairing Polymerase Chain Reaction (XPCR). The word blending between two words αwγ1 and γ2wβ that share a non-empty overlap w, results in αwβ. Interestingly, this phenomenon has been observed independently in linguistics, under the name “blend word” or “portmanteau”, and is responsible for the creation of words in the English language such as smog (smoke + fog), labradoodle (labrador + poodle), and Brangelina (Brad + Angelina). Technically, word blending is related to the binary word operation Latin product, the crossover operation, and simple splicing. We study closure properties of the families in the Chomsky hierarchy under word blending, language equations involving this operation, and its descriptional state complexity when applied to regular languages. We also define iterated word blending and show that, for a given alphabet, there are finitely many languages that can be obtained from an initial language by iterated word blending.
