https://en.formulasearchengine.com/index.php?action=history&feed=atom&title=HBJ_model 2026-04-22T01:12:53Z Revision history for this page on the wiki MediaWiki 1.43.0-wmf.28 https://en.formulasearchengine.com/index.php?title=HBJ_model&diff=28238&oldid=prev 2013-03-08T05:55:00Z

<p><a href="/index.php?title=WP:CHECKWIKI&amp;action=edit&amp;redlink=1" class="new" title="WP:CHECKWIKI (page does not exist)">WP:CHECKWIKI</a> errors fixed + general fixes, added <a href="/index.php?title=CAT:O&amp;action=edit&amp;redlink=1" class="new" title="CAT:O (page does not exist)">orphan</a> tag using <a href="/index.php?title=Testwiki:AWB&amp;action=edit&amp;redlink=1" class="new" title="Testwiki:AWB (page does not exist)">AWB</a> (8961)</p> <p><b>New page</b></p><div>In mathematics and computer science, a &#039;&#039;&#039;splicing rule&#039;&#039;&#039; is a transformation on [[formal language]]s which formalises the action of [[gene splicing]] in [[molecular biology]]. A &#039;&#039;&#039;splicing language&#039;&#039;&#039; is a language generated by iterated application of a splicing rule: the splicing languages form a proper subset of the [[regular language]]s.<br /> <br /> ==Definition==<br /> Let &#039;&#039;A&#039;&#039; be an alphabet and &#039;&#039;L&#039;&#039; a language, that is, a subset of the free monoid &#039;&#039;A&#039;&#039;&lt;sup&gt;&amp;lowast;&lt;/sup&gt;. A &#039;&#039;&#039;splicing rule&#039;&#039;&#039; is a quadruple &#039;&#039;r&#039;&#039; = (&#039;&#039;a&#039;&#039;,&#039;&#039;b&#039;&#039;,&#039;&#039;c&#039;&#039;,&#039;&#039;d&#039;&#039;) of elements of &#039;&#039;A&#039;&#039;&lt;sup&gt;&amp;lowast;&lt;/sup&gt;, and the action of the rule &#039;&#039;r&#039;&#039; on &#039;&#039;L&#039;&#039; is to produce the language<br /> <br /> :&lt;math&gt; r(L) = \{ xady : xabq, pcdy \in L \} \ . &lt;/math&gt;<br /> <br /> If &#039;&#039;R&#039;&#039; is a set of rules then &#039;&#039;R&#039;&#039;(&#039;&#039;L&#039;&#039;) is the union of the languages produced by the rules of &#039;&#039;R&#039;&#039;. We say that &#039;&#039;R&#039;&#039; &#039;&#039;respects&#039;&#039; &#039;&#039;L&#039;&#039; if &#039;&#039;R&#039;&#039;(&#039;&#039;L&#039;&#039;) is a subset of &#039;&#039;L&#039;&#039;. The &#039;&#039;R&#039;&#039;-closure of &#039;&#039;L&#039;&#039; is the union of &#039;&#039;L&#039;&#039; and all iterates of &#039;&#039;R&#039;&#039; on &#039;&#039;L&#039;&#039;: clearly it is respected by &#039;&#039;R&#039;&#039;. A &#039;&#039;&#039;splicing language&#039;&#039;&#039; is the &#039;&#039;R&#039;&#039;-closure of a finite language.&lt;ref name=A236&gt;Anderson (2006) p.&amp;nbsp;236&lt;/ref&gt;<br /> <br /> A rule set &#039;&#039;R&#039;&#039; is &#039;&#039;&#039;reflexive&#039;&#039;&#039; if (&#039;&#039;a&#039;&#039;,&#039;&#039;b&#039;&#039;,&#039;&#039;c&#039;&#039;,&#039;&#039;d&#039;&#039;) in &#039;&#039;R&#039;&#039; implies that (&#039;&#039;a&#039;&#039;,&#039;&#039;b&#039;&#039;,&#039;&#039;a&#039;&#039;,&#039;&#039;b&#039;&#039;) and (&#039;&#039;c&#039;&#039;,&#039;&#039;d&#039;&#039;,&#039;&#039;c&#039;&#039;,&#039;&#039;d&#039;&#039;) are in &#039;&#039;R&#039;&#039;. A splicing language is reflexive if it is defined by a reflexive rule set.&lt;ref name=A242/&gt;<br /> <br /> ==Examples==<br /> * Let &#039;&#039;A&#039;&#039; = {&#039;&#039;a&#039;&#039;,&#039;&#039;b&#039;&#039;,&#039;&#039;c&#039;&#039;}. The rule (&#039;&#039;caba&#039;&#039;,&#039;&#039;a&#039;&#039;,&#039;&#039;cab&#039;&#039;,&#039;&#039;a&#039;&#039;) applied to the finite set {&#039;&#039;cabb&#039;&#039;,&#039;&#039;cabab&#039;&#039;,&#039;&#039;cabaab&#039;&#039;} generates the regular language &#039;&#039;caba&#039;&#039;&lt;sup&gt;&amp;lowast;&lt;/sup&gt;&#039;&#039;b&#039;&#039;.&lt;ref name=A238&gt;Anderson (2006) p.&amp;nbsp;238&lt;/ref&gt;<br /> <br /> ==Properties==<br /> * All splicing languages are regular.&lt;ref name=A239&gt;Anderson (2006) p.&amp;nbsp;239&lt;/ref&gt;<br /> * Not all regular languages are splicing.&lt;ref name=A240&gt;Anderson (2006) p.&amp;nbsp;240&lt;/ref&gt; An example is (&#039;&#039;aa&#039;&#039;)&lt;sup&gt;&amp;lowast;&lt;/sup&gt; over {&#039;&#039;a&#039;&#039;,&#039;&#039;b&#039;&#039;}.&lt;ref name=A239/&gt; <br /> * If &#039;&#039;L&#039;&#039; is a regular language on the alphabet &#039;&#039;A&#039;&#039;, and &#039;&#039;z&#039;&#039; is a letter not in &#039;&#039;A&#039;&#039;, then the language { &#039;&#039;zw&#039;&#039; : &#039;&#039;w&#039;&#039; in &#039;&#039;L&#039;&#039; } is a splicing language.&lt;ref name=A238/&gt;<br /> * There is an algorithm to determine whether a given regular language is a reflexive splicing language.&lt;ref name=A242&gt;Anderson (2006) p.&amp;nbsp;242&lt;/ref&gt;<br /> * The set of splicing rules that respect a regular language can be determined from the [[syntactic monoid]] of the language.&lt;ref name=A241&gt;Anderson (2006) p.&amp;nbsp;241&lt;/ref&gt;<br /> <br /> == References ==<br /> {{reflist}}<br /> * {{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]] | year=2006 | isbn=0-521-61324-8 | zbl=1127.68049 }}<br /> <br /> [[Category:Semigroup theory]]<br /> [[Category:Formal languages]]<br /> [[Category:Combinatorics on words]]<br /> <br /> {{combin-stub}}</div>

en>Yobot