Splicing rule


In mathematics and computer science, a splicing rule is a transformation on formal languages which formalises the action of gene splicing in molecular biology. A splicing language is a language generated by iterated application of a splicing rule: the splicing languages form a proper subset of the regular languages.

Definition

Let A be an alphabet and L a language, that is, a subset of the free monoid A∗. A splicing rule is a quadruple r = of elements of A∗, and the action of the rule r on L is to produce the language
If R is a set of rules then R is the union of the languages produced by the rules of R. We say that R respects L if R is a subset of L. The R-closure of L is the union of L and all iterates of R on L: clearly it is respected by R. A splicing language is the R-closure of a finite language.
A rule set R is reflexive if in R implies that and are in R. A splicing language is reflexive if it is defined by a reflexive rule set.

Examples