Splicing language

In mathematics and theoretical computer science, a splicing language is a formal language which formalizes the action of gene splicing in molecular biology. Splicing languages have a variety of definitions based on the form of splicing rules allowed, which describe how one may "cut" and "paste together" strings from the language to obtain new strings. In all of them, given an initial language $I$ over a finite alphabet $\Sigma$ and a set of splicing rules $R$, a splicing language is the smallest language containing $I$ which is closed under applying any splicing rule $r\in R$.

The original definition of a splicing language was given by Head in 1987. Later on, alternative and inequivalent definitions were provided by Păun and Pixton. The class of languages generated by Head splicing is strictly contained in that of those generated by Păun splicing, which is in turn strictly contained in that of those generated by Pixton splicing.

Definition

The following definition is that of a Păun splicing system, which is most common:

Let $\Sigma$ be a finite alphabet and $I\subseteq \Sigma ^{*}$ a language. A splicing rule is a quadruple $r=(u_{1},v_{1},u_{2},v_{2})\in (\Sigma ^{*})^{4}$ (often written $r=(u_{1},v_{1};u_{2},v_{2})$). For $w_{1},w_{2}\in \Sigma ^{*}$ and a splicing rule $r=(u_{1},v_{1};u_{2},v_{2})\in (\Sigma ^{*})^{4}$, we write $(w_{1},w_{2})\vdash _{r}z$ if $w_{1}=x_{1}u_{1}v_{1}y_{1}$, $w_{2}=x_{2}u_{2}v_{2}y_{2}$, and $z=x_{1}u_{1}v_{2}y_{2}$. If $R$ is a set of splicing rules over $\Sigma$, we say that $\sigma =(\Sigma ,R)$ is an H-scheme and define the action of $\sigma$ on $I$ to be $\sigma (I)=\{z\in \Sigma ^{*}:\exists w_{1},w_{2}\in I{\text{ s.t. }}(w_{1},w_{2})\vdash _{r}z{\text{ }}\forall r\in R\}$. Now, inductively, let $\sigma ^{0}(I)=I$ and $\sigma ^{i+1}(I)=\sigma (\sigma ^{i}(I))$. $\sigma ^{*}(I)=\bigcup _{i\in \mathbb {Z} _{0}^{+}}\sigma ^{i}(I)$ is the splicing language generated by the H-system $H=(\Sigma ,I,R)$. That is, the smallest language containing $I$ and closed under applications of any $r\in R$.

A rule set $R$ is reflexive if $(u_{1},v_{1};u_{2},v_{2})\in R$ implies that $(u_{1},v_{1};u_{1},v_{1}),(u_{2},v_{2};u_{2},v_{2})\in R$. A rule set $R$ is symmetric if $(u_{1},v_{1};u_{2},v_{2})\in R$ implies that $(u_{2},v_{2};u_{1},v_{1})\in R$. A splicing language is called reflexive (resp. symmetric) if it is generated by a reflexive (resp. symmetric) H-system.

Results and Examples

A non-example of a splicing language is $(aa)^{*}$, whereas $b(aa)^{*}$ is a splicing language. In fact, if $L$ is a regular language on the alphabet $\Sigma$, and $b$ is a letter not in $\Sigma$, then the language $bL=\{bw:w\in L\}$ is a splicing language.

All splicing languages generated by a finite initial language and finite rule set are regular.

It is decidable whether or not a regular language is a splicing language and whether or not it is reflexive. Both algorithms make use of the decidability of whether or not a splicing rule respects a regular language, meaning that the language is closed under splicing by that rule.

Every regular splicing language contains a constant, which is a word $c\in \Sigma ^{*}$ such that $u_{1}cv_{1},u_{2}cv_{2}\in L$ implies that $u_{1}cv_{2},u_{2}cv_{1}\in L$ for any $u_{1},v_{1},u_{2},v_{2}\in \Sigma ^{*}$.