I. L. and R. La, + (X w 1 agt q i w2Y, Rl L) Tube 2 : Nous avons : R'Lt. Comme nous I'avons dit plus haut, nous pouvons avoir ici d'autres molécules obtenues pendant une étape précédente de calcul qui n'altèrent pas le calcul, Nous les omettrons et nous ne mentionnerons plus ce fait dans le futur. Pas d'application de règles. Communication : Les filtres courants sont

R. , X. Xu1l, and L. Rll, Molécules restant dans le tube 1 : Rf a1 S' qiu2Y, RS qiap Z {, X w 1a1 S' Qi*rY

. De, qiw2Y seraenvoyée du premier tube au deuxième tube à l'étape suivante Étape 2. Recombinaison : Tube 1 : Nous avons : Rfa$' qiu2Y, XulalSt qiut2Y, Rt L' . Nous appliquons les règles suivantes qui font partie du groupe I.2.n : (Xu1a1lS'qiu2Y, RtlLt), pp.11-13

R. Xwyl, R. R\lt, L. {r, L. St, R. et al., Pas d'application de règles Communication : Les filtres courants sont : ln{') Molécules envoyées du tube 1 au tube 2 : R' Lt , Rfafi'gi.rY, Xw1afitqiw2Y, XwplLt , Rt S'qiu2Y, RIL' ' Molécules restant dans le tube 1 : Rt S' Z 1, R\ S qiw2Y, X up1 S qiu2Y, Tube 2 : Nous avons : Xw1Sq Molécules envoyées du tube 2 au tube 1 : RL. Molécules restant dans le tube 2 : R'L' , Rf a$'Qi*rY, XwplS'qiw2Y, Xw1a1L' , R'S'qiw2Y

D. Osons-fi-m-r, . Mz, and . Rt-u-rù, Soient NUTU{B} : {ar,a2t...,an} (an: B) et B ç {N U7}. Supposons aussi que T : {orr... ran-t}. Dans ce qui suit nous supposons que : 1< i < rz, pp.0-1

:. Mr and . {zpyi, ZtWr-r,V'21,V Zy,VaZr, ZrW'n, p.1

X. Xvbw, YQn) t o't XyBwY ---+ XÇwY(i,n) t

S. and M. Avec-recombinaisoai-et-comm, L29 Nous avons donc fait tourner le mot VuapW d'une lettre, Il est possible d'appliquer les règles LIZ et 2.15 dans les cas marqués par (+) et (++), mais ces applications seront discutées plus tard

+. Vnwyt and . Xvw, Wn(out) si'tr :'utB, pp.6-13

. Dans-ce-cas, le mot u' qui est terminal est envoyé à I'extérieur et il fera partie du résultat du calcul Autres évolutions possibles : 1. (cas (++)) VuWt 2fiVw'Wt(out) (w

. Vwtwb, VwtW'n(here) t. 2. VBwWt

. Il-est-facile-de-voir and . Qu, en suivant le calcul ci-dessus nous obtenons tous les mots de I(G) et, comme nous avons considéré tous les cas possibles

C. 9. Systèmes, . Membraates, and . Recombinaiso, I{ Nous notons par ELSP*(spl,moue) la famille des langages produits par les systèmes à membranes avec recombinaison et communication immédiate de degré au plus rn Comme dans la section précédente nous n'indiquons pas le type du système considéré, car nous pouvons éviter les problèmes qui nous ont obligé à examiner différentes variantes. Si on a une seule membrane, à chaque étape du calcul nous envoyons les mêmes molécules à I'extérieur lesquelles sont

L. Est-défini-par, N. Utu-{b}-u-{x, Y. Xi, Y. Xo, . Yo et al., L'alphabet terminal ? est celui de la grammaire formelle G. Les axiomes sont définis par : Mr : {X, M2 : {XiaiZ Les règles du système sont définis de la manière suivante. Règles de .R1 : (Xwla6Y, ZIV) -.t.z

L. M. Adleman, Molecular computation of solutions to combinatorial problems. Sc'ience, pp.266-293, 1994.

P. Bonizzoni, C. D. Felice, G. Mauri, and R. Zizza, Regular Languages Generated by Reflexive Finite Splicing Systems, Proceedings of Deueloprnents'in Language Theory 2003, DLT03 27L0 of. Lecture Notes in Computer Sc'ience, pp.34-45, 2003.
DOI : 10.1007/3-540-45007-6_10

P. Bonizzoni, C. D. Felice, G. Mauri, and R. Zizza, The structure of reflexive finite splicing languages via Schùtzenberger constants, 2004.

J. Cocke and M. Minsky, Universality of Tag Systems with P = 2, Journal of the ACM, vol.11, issue.1, pp.15-20, 1964.
DOI : 10.1145/321203.321206

E. Csuhaj-varjri, L. Kari, and G. Pàun, Test tube distributed systems based on splicing. Computers and A1, pp.211-232, 1996.

K. Culik, I. , and T. Harju, Splicing semigroups of dominoes and DNA. Discrete Appli, pp.31-57, 1991.

F. Freund, R. Reund, M. Margenstern, M. Oswald, Y. Rogozhin et al., P Systems with Cutting/Recombination Rules Assigned to Membranes, Preproceed'ings of the Workshop on Membrane Computi,ng. Tarragona
DOI : 10.1007/978-3-540-24619-0_14

R. and F. Fteund, Test tube systems : when two tubes are enough, Preproceed'ings of DLT99, Deuelopments in Language Theory, pp.275-286, 2000.

P. Fyisco and C. Zandron, On variants of communicating distributed H systems, Fundamenta Inf ormati, vol.cae, issue.1, pp.48-57

T. E. Goode-laun, Constants and Splicing Systems, 1999.

T. Head, Formal language theory and DNA : an analysis of the generative capacity of specific recombinant behaviors, Bulletin of Mathematical Biologg, vol.4, issue.6, pp.737-759, 1987.

T. Head, Splicing languages generated with one sided context Computing with Bio-Molecules. Theory and Erperimenfs, pp.158-181, 1998.

T. Head, G. Pàun, and D. Pixton, Language Theory and Molecular Genetics: Generative Mechanisms Suggested by DNA Recombination, Hand,book of Forrnal Languages, 3 aolumes 1471, pp.295-360
DOI : 10.1007/978-3-662-07675-0_7

J. Hopcroft, R. Motwani, and J. Ullman, Introducti,on to Automata Theory, Languages, and Computation, 2001.

L. Kari, DNA computing : arrival of biological mathematics Earlier version under the title DNA computers, tomorrow's reality. Bulletin of the European Association for Theoretical Computer Science, The Mathematical Intelligencer, vol.19, issue.259, pp.9-22256, 1996.

S. M. Kim, An algorithm for identifying spliced languages, Proceed'ings of Cocoon97, pp.403-411, 1997.
DOI : 10.1007/BFb0045107

S. Kleene, Introduction to Metamathematics, 1952.

R. J. Lipton, DNA solution of hard computational problems, Science, vol.268, issue.5210, pp.542-545, 1995.
DOI : 10.1126/science.7725098

V. Manca, A proof of regularity for finite splicing Aspects of Molecular Computing. Essays Dedi,cated to Tom Head on the Occasion of Hi,s 70th Bi,rthday, pp.9-309, 2004.

M. Margenstern and Y. Rogozhin, Generating all recursively enumerable languages with a time-varying distributed H system of degree 2, 1999.

M. Margenstern and Y. Rogozhin, A universal time-varying distributed Hsystem of degree 2, Proceedings of the 4fih DIMACS meeti,ng on DNA based compufers, pp.9991-373

M. Margenstern and Y. Rogozhin, About time-varying distributed H systems
DOI : 10.1007/3-540-44992-2_5

M. Margenstern and Y. Rogozhin, Time-varying distributed H systems of degree 2 generate all recursively enumerable languages, pp.399-407

M. Margenstern and Y. Rogozhin, Extended time-varying distributed H systems -universality result In Proceed,i,ngs of The ïth World Multi-Conference on Systemi, 2001.

M. Margenstern, Y. Rogozhin, M. Ito, G. Pàun, and S. Yu, Time-varying distributed H systems of degree 1-generate all recursively enumerable languages, Semi,groups, and Tfansductions, pp.329-340, 2001.

M. Margenstern and Y. Rogozhin, A universal time-varying distributed H system of degree 1 Reui,sed Papers, DNA Computi,ng : Tth International Workshop on DNA-Based Computers, pp.371-380, 2001.

M. Margenstern, Y. Rogozhin, and S. Verlan, Time-Varying Distributed H Systems of Degree 2 Can Carry Out Parallel Computations, DNA Computing : 8th International Worlcshop on DNA- Based Computers, DNA| of Lecture Notes i,n Computer Sc'ience, pp.326-336, 2002.
DOI : 10.1007/3-540-36440-4_29

URL : https://hal.archives-ouvertes.fr/hal-01352360

M. Margenstern, Y. Rogozhin, and S. Verlan, Time-Varying Distributed H Systems with Parallel Computations: The Problem Is Solved, Preli,minary Proceed ,'ings of DNA Computing, 9th internati,onal Worlcshop on DNA-Based Computers, pp.1-447, 2003.
DOI : 10.1007/978-3-540-24628-2_6

URL : https://hal.archives-ouvertes.fr/hal-01352355

C. Martin-vide, G. Pàun, and A. Rodriguez-patôn, P systems with immediate communication, Romanian Journal of Informati,on Sci,ence and Technology, vol.4, issue.2, pp.7-82, 2001.

M. Minsky, computations : Fi,nite and Infini,te Machi,nes, 1967.

D. Pixton, Regularity of splicing languages, Discrete Applied Mathematics, vol.69, issue.1-2, pp.701-124, 1996.
DOI : 10.1016/0166-218X(95)00079-7

L. Priese, Y. Rogozhin, and M. Margenstern, Finite H-systems with 3 test tubes are not predictable, Proceedings of Paci,fic Symposi'um on B'iocomput'ing, pp.547-558, 1998.

A. Pàun, On time-varying H systems, Bulleti,n of EATCS, vol.67, pp.157-158, 1999.

A. Pàun and M. Pàun, On the membrane computing based on splicing, Martin-Vide and Mitrana 131, pp.409-422

G. Pàun, On the splicing operation Discrete Appli, Mathematics, vol.70, issue.1, pp.57-79, 1996.

G. Pàun, Regular extended H systems are computationally universal, JALC, vol.1, issue.1, pp.27-36, 1996.

G. Pàun, DNA computing : distributed splicing systems Computer Science. A Selection of Essays ,in Honor of A. EhrenJezchf, Structures in Logic and, pp.351-370, 1997.
DOI : 10.1007/978-3-662-03563-4

G. Pàun, DNA computing based on splicing: universality results, Proceedings of the Second, Internetional Colloquium on (Jn'iuersal Machines and, Computations, pp.67-76, 1998.
DOI : 10.1016/S0304-3975(99)00104-8

G. Pàun, Computing with membranes, Journal of Computer and System Sc'iences, pp.108-143, 1998.

G. Pàun, DNA computing based on splicing : universality results. Theoretical Computer Sc'ience, Journal version, vol.2340, issue.2, pp.275-296, 2000.

G. Pàun, Membrane Computi,ng. An Introduction, 2002.

G. Pàun, G. Rozenberg, and A. Salomaa, DNA Computing : New Computi,ng Paradigms
DOI : 10.1007/978-3-662-03563-4

G. Pàun and T. Yokomori, Membrane computing based on splicing, DNA Baseil Computers I DIMACS Series in Discrete Mathematics and Theoreti,cal C omputer S cience, pp.2-7

Y. Rogozhin, Small universal Turing machines, Theoretical Computer Science, vol.168, issue.2, pp.215-240, 1996.
DOI : 10.1016/S0304-3975(96)00077-1

URL : https://doi.org/10.1016/s0304-3975(96)00077-1

G. Rozenberg and A. Salomaa, Handboolc of Formal Languages

. Tvdhsim, Time-varying distributed H systems simulator

S. Verlan, On extended time-varying distributed H systems, Preproceedi,ngs at 6th International Workshop on DNA-Based Computers, p.281, 2000.

S. Verlan, Calculs Moleculai,res : Ies Systèmes Distribués à Changement de Phase, 2001.

S. Verlan, On enhanced time-varying distributed H systems, Computer Sc'ience Journal of Moldoua, vol.0, issue.3, pp.263-279, 2002.
URL : https://hal.archives-ouvertes.fr/hal-01352361

S. Verlan, About splicing P systems with immediate communication and nonextended splicing P systems, Preproceedings of the Workshop on Membrane Computing. Tarragona, pp.461-473, 2003.
URL : https://hal.archives-ouvertes.fr/hal-01352359

S. Verlan, A frontier result on enhanced time-varying distributed H systems with parallel computations, Preproceed,ings of DCFS'03, Descriptional Complerity of Formal Systems, pp.22-232, 2003.
URL : https://hal.archives-ouvertes.fr/hal-01352357

S. Verlan, Communicating Distributed H Systems with Alternating Filters, Aspects of Molecular Computing . Essays Dedicated to Tom Head, on the Occasion of Hi,s 70th Bi,rthday, . [41
DOI : 10.1007/978-3-540-24635-0_29

URL : https://hal.archives-ouvertes.fr/hal-01352420

S. Verlan and R. Zizza, l-splicing vs. 2-splicing : separating results, Proceedings of WOilDS'\?, Turleu, Fi'nland, pp.320-331, 2003.

W. Wordsworth, The tables turned In Wordworth's Poems, 1965.

C. Zandron, The P systems web page

C. Zandron, C. Ferretti, and G. Mauri, A reduced distributed splicing system for RE languages New trends i,n Formal Language. Control, cooperatio, and conbinatorics, Computer Science, vol.1218, pp.346-366, 1997.

C. Zandron, C. Ferretti, and G. Mauri, Nine test tubes generate any RE language, Theoretical Computer Sc'ience, pp.171-180, 2000.

R. Zizza, On the pouer of classes of spli,cing systems, 2002.