Splicing rule

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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 = (a,b,c,d) of elements of A, and the action of the rule r on L is to produce the language

 r(L) = \{ xady : xabq, pcdy \in L \} \ .

If R is a set of rules then R(L) is the union of the languages produced by the rules of R. We say that R respects L if R(L) 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.[1]

A rule set R is reflexive if (a,b,c,d) in R implies that (a,b,a,b) and (c,d,c,d) are in R. A splicing language is reflexive if it is defined by a reflexive rule set.[2]

Examples[edit]

  • Let A = {a,b,c}. The rule (caba,a,cab,a) applied to the finite set {cabb,cabab,cabaab} generates the regular language cabab.[3]

Properties[edit]

  • All splicing languages are regular.[4]
  • Not all regular languages are splicing.[5] An example is (aa) over {a,b}.[4]
  • If L is a regular language on the alphabet A, and z is a letter not in A, then the language { zw : w in L } is a splicing language.[3]
  • There is an algorithm to determine whether a given regular language is a reflexive splicing language.[2]
  • The set of splicing rules that respect a regular language can be determined from the syntactic monoid of the language.[6]

References[edit]

  1. ^ Anderson (2006) p. 236
  2. ^ a b Anderson (2006) p. 242
  3. ^ a b Anderson (2006) p. 238
  4. ^ a b Anderson (2006) p. 239
  5. ^ Anderson (2006) p. 240
  6. ^ Anderson (2006) p. 241