Splicing Languages and DNA:
A Survey

Tom Head

Dept. of Mathematical Sciences
Binghamton University
Binghamton, New York 13902-6000, USA
e-mail: tom@math.binghamton.edu

The concept of a splicing scheme has been developed for the purpose of introducing into formal language theory a convenient representation of the cut and paste operations carried out on double stranded DNA using restriction enzymes and a ligase. A splicing language is the set of all strings that may arise from an initial language under repeated operation by a splicing scheme. During the last decade a dozen researchers have contributed theorems elucidating the actions of splicing schemes and the structure of splicing languages. These results and the new problems they suggest are surveyed. Emphasis is placed on very recent research that has not yet been published. Special regard is given to results that treat the unified interaction of circular and linear strings.