Reguła splicingu

W matematyce i informatyce reguła splicingu to transformacja języków formalnych , która formalizuje działanie splicingu genów w biologii molekularnej . Język splicingu to język generowany przez iteracyjne stosowanie reguły splicingu: języki splicingu tworzą odpowiedni podzbiór języków regularnych .

Definicja

Niech A będzie alfabetem, a L językiem, czyli podzbiorem wolnej monoidy A ^∗ . Reguła splicingu to poczwórna r = ( a , b , c , d ) elementów A ^∗ , a działaniem reguły r na L jest utworzenie języka

${\ Displaystyle r (L) = \ {xady: xabq, pcdy \ w L \} \.}$

Jeśli R jest zbiorem reguł, to R ( L ) jest sumą języków utworzonych przez reguły R. Mówimy, że R szanuje L , jeśli R ( L ) jest podzbiorem L. R - zamknięcie L jest połączeniem L i wszystkich iteracji R na L : wyraźnie jest przestrzegane przez R . Językiem splicingowym jest R -domknięcia języka skończonego.

Zestaw reguł R jest zwrotny, jeśli ( a , b , c , d ) w R implikuje, że ( a , b , a , b ) i ( c , d , c , d ) są w R. Język splicingu jest zwrotny, jeśli jest zdefiniowany przez zbiór reguł zwrotnych.

Przykłady

• Niech A = { za , b , do }. Reguła ( caba , a , cab , a ) zastosowana do zbioru skończonego { cabb , cabab , cabaab } generuje język regularny caba ^∗ b .

Nieruchomości

• Wszystkie języki splicingu są regularne.
• Nie wszystkie języki regularne są splatane. Przykładem jest ( aa ) ^∗ nad { a , b }.
• Jeśli L jest językiem regularnym w alfabecie A , a z jest literą spoza A , to język { zw : w w L } jest językiem splicingowym.
• Istnieje algorytm określający, czy dany język regularny jest językiem splicingu refleksyjnego.
• Zestaw reguł splicingu, które respektują język regularny, można określić na podstawie monoidu składniowego języka.

•    Anderson, James A. (2006). Teoria automatów z nowoczesnymi zastosowaniami . Z udziałem Toma Heada. Cambridge: Cambridge University Press . ISBN 0-521-61324-8 . Zbl 1127.68049 .