Tom Head and Dennis Pixton and Elizabeth Goode
Splicing Systems: Regularity and Below (dvi, pdf, postscript)
in DNA Computing, 8th International Workshop on DNA Based Computers, DNA8, Sapporo, Japan, June 10-13, 2002, Revised Papers (M. Hagiya and A. Ohuchi, eds.), Lecture Notes in Computer Science, v. 2568, Springer-Verlag, 2003, pp. 262--268.

The motivation for the development of splicing theory is recalled. Attention is restricted to finite splicing systems, which are those having only finitely many rules and finitely many initial strings. Languages generated by such systems are necessarily regular, but not all regular languages can be so generated. The splicing systems that arose originally, as models of enzymatic actions, have two special properties called reflexivity and symmetry. We announce the Pixton-Goode procedure for deciding whether a given regular language can be generated by a finite reflexive splicing system. Although the correctness of the algorithm is not demonstrated here, two propositions that serve as major tools in the demonstration are stated. One of these is a powerful pumping lemma. The concept of the syntactic monoid of a language provides sharp conceptual clarity in this area. We believe that there may be yet unrealized results to be found that interweave splicing theory with subclasses of the class of regular languages and we invite others to join in these investigations.