View Related Documents

Abstract

The motivation for the development of splicing theory is recalled. A ttention 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.Th e 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.A lthough 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.Th e 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.

Fulltext Preview

Image of the first page of the fulltext document