Minimality in template-guided recombination

Ciliates are unicellular organisms, some of which perform complicated rearrangements of their DNA. Template-guided recombination (TGR) is a formal model for the DNA recombination which occurs in ciliates. TGR has been the subject of much research in formal language theory, as it can be viewed as an operation on formal languages. In TGR, a set of templates serves as a parameter to a language operation which controls which rearrangements can take place; thus, a set of templates is itself a language.Recently, the concept of equivalence in TGR has been considered: given two sets of templates, do they define the same language operation? This paper considers the related question of minimality: given a set of templates T, what is the smallest set of templates (with respect to inclusion) equivalent to T? We show that the minimal set of templates is unique, and consider closure properties and decidability questions related to minimality. We define an operational characterization for equivalence which is useful for results on minimality.