Splicing in abstract families of languages

AbstractWe show that the iterated splicing operation determined by a regular H scheme (with some necessary restrictions) preserves membership in any full abstract family of languages. This involves translation of an H scheme into two alternative forms. The first form, which is closely related to the underlying biochemical operations, uses cutting and pasting rather than splicing. The second form uses matrices of languages, and in this formulation the splicing operation is translated into standard formal language operations (concatenation and quotient). Moreover, in the matrix formulation the splicing language itself may be expressed in terms of standard formal language operations, and this provides an algorithm for calculating the splicing language. As an application we use the cutting and pasting approach to extend the closure result to circular strings