Splicing semigroups of dominoes and DNA

The authors introduce semigroups of dominoes as a tool for working with sets of linked strings. In particular, they are interested in splicing semigroups of dominoes. In the special case of alphabetic (symbol-to-symbol linked) dominoes the splicing semigroups are essentially equivalent to the splicing systems introduced by Head to study informational marcomolecules, specifically to study the effect of sets of restriction enzymes and ligase that allow DNA molecules to be cleaved and reassociated to produce further molecules. The present main result is that in the case of alphabetic dominoes the splicing semigroup generated from an initial regular set is again regular. This implies positive solution of two open problems stated by Head, namely the regularity of splicing systems and the decidability of their membership problem.