In mathematics and computer science, a splicing rule is a transformation on

formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of symb ...

s which formalises the action of

gene splicing Recombinant DNA (rDNA) molecules are DNA molecules formed by laboratory methods of genetic recombination (such as molecular cloning) that bring together genetic material from multiple sources, creating sequences that would not otherwise be foun ...

molecular biology Molecular biology is the branch of biology that seeks to understand the molecular basis of biological activity in and between cells, including biomolecular synthesis, modification, mechanisms, and interactions. The study of chemical and physi ...

. A splicing language is a language generated by iterated application of a splicing rule: the splicing languages form a proper subset of the

regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...

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

r(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.Anderson (2006) p. 236 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.

Examples

* Let ''A'' = . The rule (''caba'',''a'',''cab'',''a'') applied to the finite set generates the regular language ''caba''^∗''b''.Anderson (2006) p. 238

Properties

* All splicing languages are regular.Anderson (2006) p. 239 * Not all regular languages are splicing.Anderson (2006) p. 240 An example is (''aa'')^∗ over . * If ''L'' is a regular language on the alphabet ''A'', and ''z'' is a letter not in ''A'', then the language is a splicing language. * There is an algorithm to determine whether a given regular language is a reflexive splicing language.Anderson (2006) p. 242 * The set of splicing rules that respect a regular language can be determined from the

syntactic monoid In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L. Syntactic quotient The free monoid on a given set is the monoid whose elements are all the strings of zero ...

of the language.Anderson (2006) p. 241

References

* {{cite book , last=Anderson , first=James A. , title=Automata theory with modern applications , others=With contributions by Tom Head , location=Cambridge , publisher=

Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by Henry VIII of England, King Henry VIII in 1534, it is the oldest university press A university press is an academic publishing hou ...

, year=2006 , isbn=0-521-61324-8 , zbl=1127.68049 Semigroup theory Formal languages Combinatorics on words