TEST TUBE SYSTEMS WITH

TEST TUBE SYSTEMS WITH CUTTING/RECOMBINATION OPERATIONS

Rudolf FREUND Institut fur Computersprachen, Technische Universitat Wien

Resselgasse 3, 1040 Wien, Austria email: rudi@logic.tuwien.ac.at Erzsebet CSUHAJ-VARJU

Computer and Automation Institute, Hungarian Academy of Sciences Kende u. 13-17, 1111 Budapest, Hungary email: csuhaj@luna.aszi.sztaki.hu Franz WACHTLER

Institut fur Histologie und Embryologie, Universitat Wien Schwarzspanierstr. 17, 1090 Wien, Austria email: franz.wachtler@univie.ac.at

We introduce test tube systems 1;2;3;9 based on operations that are closely related to the splicing operation8, i.e. we consider the operations of cutting a string at a specic site into two pieces with marking them at the cut ends and of recombining two strings with specicly marked endings7. Whereas in the splicing of two strings these strings are cut at specic sites and the cut pieces are recombined immediately in a crosswise way, in CR(cutting/recombination)-schemes cutting can happen independently from recombining the cut pieces. Test tube systems based on these operationsof cutting and recombinationturn out to have maximalgenerative power even if only very restricted types of input lters for the test tubes are used for the redistribution of the contents of the test tubes after a period of cuttings and recombinations in the test tubes.

1 Introduction

TDeNstAtmuboelecsyusletsem1;2s;3w;9e,rteheinptrraocdtuiccaeldsoalsutbiioonloogficNaPl cpormobpluetmers

systems based on with such systems

wstpualbsicedinseygsscotrepimbeersadtb,iaoasnneddwetorhneetitnhhveeeoosptrieegtraiacttaeildonf4e.saIotnuf rtcehusitstoipfnatgpeasetnr dtwuerbeaecroesmygsbotiiennmagtstioobnaexs7epadlnoodrenwtteihtshet

input lters which only allow specic parts of the contents of the other test

tubes to pass (such lters, for example, are conceivable for DNA molecules by

combining the principles of anity chromatography and in-situ-hybridization).

As we shall show even very restricted kinds of such lters testing for the ex-

istence respectively non-existence of specic markings allow for reaching the

generative power to generate any recursively enumerable language.

for

tTeshtetucboemspyusttaemtiosnbaalsuedniovnertshaelistypliocfinsgpeocpiercatviaornia4nhtassobfeHenspyrsotevmeds

5;10 and recently.

In this paper we shall show that universal test tube systems based on cutting

and recombination rules exist for dierent variants of input lters.

In the second section of this paper we dene the notions from formal

language theory needed in this paper and introduce the formal denitions of

cutting/recombination schemes (CR-schemes). In the third section of this pa-

per we introduce test tube systems with cutting/recombination rules (CRTTS)

and we prove that CRTTS can generate every recursively enumerable language.

This result also implies the existence of universal CRTTS. A short summary

of the results obtained in this paper and an overview of future research topics

conclude the paper.

2 Denitions and Examples

In we

tshhiasllsenceteidoninwtehiosnplaypdeer. nMeosroemoveernowteiornescaflrlotmhefdoremnailtiloannsgufoargCe Rth-escohryemthesa7t

and give some explanatory examples. mTheenTtlsehnaegretfhrceaeolflmeadossnttorriiindngggsweonreinrwaVotreddsisboyvwertrihtVete;anlpaihssatjbwheejt:emV pitsydsetnriontge,dVb+y

V =

, V

itsfelge-.

ooaiaaaSsffnn2(2gdddssreyyAAan((ttmmVVrmwintaNNgbgboeemnrr)doosa[a[slalimtmsssitrVfrVe,iivmmwtTTasniec.ni))agaoeht+cdrsrf.hel:.ompuosGVFstTcrn;uehNoohvlhrdeiryeseaeum2\tniacowafedltVf(p-ioxLVfqoT thrSNnuhw=ea(saeeGi=bos[2durerl)odraateV;fu=Vnlsv;TapottNgxtr)hfilauii.e;;eopenwany;.nildg(ofneV2w2eon`ytNr(e-agh Vm(Vt=;eVeeTtNi+nVmrhNs(ueamT;eojrdlVn[;pairS;ePTnvethnVaea;;`ao)flTgdPlSosb t;e)ore)e)sbnwwdyt;;syew;mohrwbwortGmaebyi:fhhlhrtoeeeeeeti`lwsesrrpd ex;rearemy:orVV `,2idiTNv nuw=aa(cyteiVlitsi:soiN(scoVnTaayan[Nmnhr(((e;eVbaVlonTnar;llTiesits)ttio ;+;eoe)Pe))nPtx2a)a(iss`nvk1eePiid eetts)s

ereexnciusumtrAsseiarvsaeubgbrilsfeae.matTnmLdhaeoronffGalymVtT+iihlfyabitsoofgtceh(anlelL-efrrdaeatener)sedcrLueitcr;susiir.cvesoei.vmlyeLplyel(neGemun)meu=nemtr,aeLrbV:alTeb+MlienforlLaaenon; vdgaeurroea,ngLrleyesciuaisfrncsdtaihvlteleherldyee

family of (-free) recursive languages over the by ENUM (VT ) and REC (VT ) ; respectively.

alphabet

VT

shall

be

denoted

for eAvegrryaLmm2aErNscUheMme(V TU)wthitehre Uex=ist(sVaNw; VoTrd; PA)Lisscuaclhletdhuant itvheersgarla(mfomr aVrTG) iLf with GL = (VN ; VT ; P; AL) generates L: One of the important results of formal language theory is that for every VT such a universal grammar

U exists.

Denition 1. A cutting/recombination scheme (or a CR-scheme) is a quadru-

ple = (V; M; C; R); where V is a nite alphabet; M is a nite set of markings;

V and where

uM2aVred[isjMoinVt;sevts;2CV

is

a [

VsetMof;

cutting and m;

rules of l 2 M;

the and

form #; $

u#l$m#v; are special

symbols not in V [M; R M M is the recombination relation representing

the recombination rules.

Cutting and recombination rules are applied to objects from O (V; M); where we dene

O (V; M) = V + [ MV [ V M [ MV M;

(2)

i.e., as the empty word has no meaningful representation in nature, is not

considered to be an object we have to deal with.

(y;

For z) if

x; y; and

zon2lyOif(Vfo;rMso)maneda2cuVttin[gMruVle

c= and

u#l2$mV# v[

wVeMdewnee

x `c have

x= rule and

uv and

r

= 2

(Vl;m[)

y = ul; z = mv: For x; y; z 2 O (V;

VfromMRwwe ehdaevenxe

(x; y) = l;

`r z y=

if and only m; and z

M) and a if for some

rec2omV bi[nMatiVon

= : For a CR-scheme

= (V; M; C; R) and any language L O (V; M) we write

(L) = fy j x `c (y; z) or x `c (z; y) for some x 2 L; c 2 Cg[ fz j (x; y) `r z for some x; y 2 L; r 2 Rg ;

(3)

andiw(eL)defonre

(L) all i

= 0:

S

i0

i(L);

where

0

(L)

=

L

and

i+1

(L)

=

i

(L)

[ 2

recomThbuinsati(oLn)rucolenttaoinosbjaelcltsobfrjoemctsLo;bta(iLne)disbtyheapsmplaylilnegstosnuebsceuttotifnOg

or (V;

one M)

that contains L and is closed under the cutting and recombination rules of :

There is a close relationship between CR schemes and splicing schemes (H schemes): For short, a splicing rule u1#v1$u2#v2 being applied to two strings

xudxcoi111aru#urt11ee[vsl[mym1pyo]b]+1n+yd$a;asn[pm[dmtpo]lx]y2ci#unuvg21tvvty1ti21nhyage2anndrtyedhicueeol2xmd#s2stubr[t2iminhn[ameg]+tsi]to+$wxn[o;1mur[su]1mtlvre]1i#nyg1vv[ms22ayx]an2+1ndu;db1[yxmvr22e]uucyso22ivmn2agibynn2idntahiixnnec2gtruooct2ushsvttweh1tmiyeins1gesiwtmwrrhiuamnilycgee.hss-

upo#si[tIminv]e+th$e[[mmfo]]+llovw;ainni.gde.wtehtehsehnaemlglaartreikvsietnrgicst[mgoe]unresrealvtveeedrssitobony

cutting rules of the form the cutting rule are the of [m] : In this case the

dcuexrtuitvi[namgti]o+rnu; l[omef]uth#vey[mtw]i+on$pa[ammrt]osrex#udve[;mpii].c+et.i;ve[mtwh]eayvdcyearnifvroabmteioentxhpexrueosvbsyejdec`tbuy#xu[xmvu]y+$jb[myv] yt#h`ve

xu

[m]+

;

[m]

vy :

[m]

The following introduced above,

ie.xe.amthpelemsharokwins gtshe[mc]h+emanicdal[mb]ack, grreospuencdtivoeflyth, econroretasptioonnds

to the positive and negative charges of ions:

Example 1. Consider the salt molecule NaCl; which in water dissipates to

tcthhueettifinoogrnmsruaNllead+Neriava#antd[imoCn]+ls$te.[pmT]Nhai#s CrjelatCcotliot`hnecmoNroralee[scmpuo]l+ned;sst[mritn]ogaCNplpalCy:ilOn;gbwvthihioceuhsfloyyriemtlhdaesl

two rule

pa[mrts]+N;

a [m]+

[m]

; ;

[m] i.e.

[m]

CNlac[amn]b+e;

recombined

[m] Cl `

to N N aC

aCl l:

by

the

recombination 2

3 CR Test Tube Systems

In this section we introduce test tube systems 1;2;3;9 that are based on the for-

mal operations of cutting and recombination rules as introduced in the previ-

ous section. The idea of test tube systems is to describe computational devices

where the computations in each test tube are based on specic operations and

any computation is done in a distributed way. As a communication step the

resulting contents of the test tubes then is redistributed according to specic

constraints, i.e. the contents of each test tube is distributed to all test tubes

according to tube. These

specic input lters again, whereas the rest remains in the ideas have already been formalized for the splicing operation

4t;eisnt

the following we dene test tube systems where the operations that can take

place in one test tube are cuttings and recombinations and investigate the

generative power of these systems with the operations of cuttings and recom-

binations. We shall show that every recursively enumerable language can be

generated by such a test tube system which only needs a very special restricted

kind of input lters. Moreover, this result also guarantees the existence of a

universal test tube system with cuttings and recombinations.

Denition 2. A test tube system with cuttings and recombinations (a CRTTS

for short) is a quintuple (V; M; A; n; ; I) ; where

1. V is a (nite) set of symbols;

2. M is a (nite) set of markings; M and V are disjoint sets;

3. A is a (nite) set of axioms, which are elements from O (V; M) ;

4. n; n 1; is the number of test tubes;

5. is a (nite) sequence (1; :::; n) ; where i = (Ci; Ri) is a nite set of

test tube operations of cuttings and recombinations, respectively, in the

test tube Ti; i.e. Ci is a (nite) set of cutting rules over (V; M) and Ri

is a the

(nite) set of recombination corresponding CR-scheme;

rules

over

(V;

M

)

;

i

=

(V;

M;

Ci;

Ri)

is

6.

ITi=; 1(I1;i:::;

In) n:

;

where

Ii

O (V; M )

is

the

input

lter

for

the

test

tube

The computations in the system run as follows: At the beginning of

the computation the axioms to the corresponding input

are distributed over the lters Ii, i.e. Ti starts

nwittehstAtu\beIsi:TNi oawccolredtinLgi

btsctrceuheooessrmbettrtseiphttnseuueppipbtou(acenLtiotsdintio)hittnnleehtnsgneeCrtiinsnrSRIepjo-d1usfiictscsjhTtodreinilmnibtssaei(tuestrrttsiisibt.ohi(uonFLetofreipooabd)mefle\lrtgasoiItitnjiertn()sih(LniLenogig)insrt)eefomoLosrvtfnoiae;mlatriynui.asbtdeVhl.eeli+ersnwitpvTeteTaahsjittro;a:itbto1tTtnucaihbaisenn(etjLsebpian)ei.ca\(neclLxoTI;rijrth)wedrtsae:ihhunncTealtgtrethiednteapoosfafenrsattteoshhhcxemheeets

the nal test tube T1:

More formally, an instantaneous description (ID for short) of the system

tiAshi\e(sAcIaoi\n:nLtnIe1e-nt;ttu:s(:p:L;ol1Aef (t(\teL)sIt1;n;:t::)u::;:;b;n.()it)aaw)ttidttthiehmneLoebiteetg=tihnOen0(iInVtDhg;eMaotft)eats;itdm1eteruitbv;iaetsthioTennni;scowtonehnepte.adreiTenrLhivteihaidetnieoiastncxiarisiolbtmIeeDpss

with

the

system yields Li (t + 1) =

=

thSeiiS1I((D1LLjii(jL((ntt1n))))(tnnjj+((LLS1jji)1(((;ttL:)j):):i);\(nLt\()In)i(Ii\ti(+SL[[i11()t)j);)nw\IhIjejr)e:

(4)

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download