Splicing language

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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_1u_1v_1y_1 , w_2=x_2u_2v_2y_2 , and z=x_1u_1v_2y_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. 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_1cv_1,u_2cv_2\in L implies that u_1cv_2,u_2cv_1\in L for any u_1,v_1,u_2,v_2\in\Sigma^* . b(aa)^*\cup(aa)^*b\cup(aa)^* is a reflexive splicing language which is not symmetric. It is also generated by a finite splicing system. a^*ba^*ba^*\cup a^*ba^*\cup a^* is a splicing language generated by a finite splicing system which is neither reflexive nor symmetric.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1316024621 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001316024621 · captured 1760052555.0 · version history

Cite this page as: encyclopegia.org, “Splicing language”, snapshot enwiki-001316024621. https://encyclopegia.org/a/splicing-language

Sources cited in this revision

9 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.