Computing with cells: membrane systems – some complexity issues

References

• Alhazov , A. , Freund , R. and Oswald , M. 2005 . “ Symbol/membrane complexity of P systems with symport/antiport rules ” . In Pre-Proceedings of the 6th International Workshop on Membrane Computing, WMC6 , Edited by: Freund , R. , Lojka , G. , Oswald , M. and Păun , Gh. 123 – 146 . Vienna : Vienna Technological University .
   Google Scholar
• Alhazov , A. , Freund , R. and Rogozhin , Y. 2006 . “ Computational power of symport/antiport: history, advances and open problems ” . In Membrane Computing, International Workshop, WMC6, Vienna, Austria, 2005, Selected and Invited Papers , Edited by: Freund , R. , Păun , Gh. , Rozenberg , G. and Salomaa , A. 1 – 30 . Berlin : Springer-Verlag . Lecture Notes in Computer Science 3850
   Google Scholar
• Cardelli , L. 2005 . “ Brane calculi. Interactions of biological membranes ” . In Computational Methods in Systems Biology. International Conference CMSB 2004, Paris, France, May 2004, Revised Selected Papers , Edited by: Danos , V. and Schachter , V. 257 – 280 . Berlin : Springer-Verlag . Lecture Notes in Computer Science 3082
   Google Scholar
• Cheruku , S. 2007 . Simulating FAS-induced apoptosis by using P systems . Prog. Nat. Sci. , 17 ( 4 ) : 424 – 431 .
   Web of Science ®Google Scholar
• Ciobanu , G. and Wenyuan , G. 2004 . “ A P system running on a cluster of computers ” . In Membrane Computing. International Workshop, WMC2003, Tarragona, Spain, Revised Papers , Edited by: Martín-Vide , C. , Mauri , G. , Păun , Gh. , Rozenberg , G. and Salomaa , A. 123 – 139 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 2933
   Google Scholar
• G. Ciobanu et al., P systems with minimal parallelism, Theor. Comput. Sci. 378(1) (2007), pp. 117–130.
   Google Scholar
• Ciobanu , G. , Păun , Gh. and Pérez-Jiménez , M. J. , eds. 2006 . Applications of Membrane Computing , Berlin : Springer .
   Google Scholar
• Csuhaj-Varju , E. , Ibarra , O. H. and Vaszil , G. 2005 . “ On the computational complexity of P automata ” . In Proceedings of DNA10 Conference, Milano, 2004 , Edited by: Ferretti , C. , Mauri , G. and Zandron , C. 76 – 89 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 3384
   Google Scholar
• Dang , Z. and Ibarra , O. H. 2004 . “ On P systems operating in sequential and limited parallel modes ” . In Pre-Proceedings of the Workshop on Descriptional Complexity of Formal Systems, DCFS , 164 – 177 . London : University of Western Ontario .
   Google Scholar
• Freund , R. 2005 . “ Asynchronous P systems and P systems working in the sequential mode ” . In Membrane Computing. International Workshop WMC5, Milan, Italy, 2004. Revised Papers , Edited by: Mauri , G. , Păun , Gh. , Pérez-Jiménez , M. J. , Rozenberg , G. and Salomaa , A. 36 – 62 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 3365
   Google Scholar
• Freund , R. and Păun , A. 2003 . “ Membrane systems with symport/antiport rules: universality results ” . In Proceedings of the WMC-CdeA2002 , 270 – 287 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 2597
   Google Scholar
• Freund , R. 2005 . Computationally universal P systems without priorities: two catalysts suffice . Theor. Comput. Sci. , 330 ( 2 ) : 251 – 266 .
   Google Scholar
• Freund , R. , eds. 2005 . Pre-Proceedings of the 6th International Workshop on Membrane Computing, WMC6 , Vienna : Vienna Technological University .
   Google Scholar
• Freund , R. , eds. 2006 . Membrane Computing, International Workshop, WMC6, Vienna, Austria, 2005, Selected and Invited Papers , Berlin : Springer-Verlag . Lecture Notes in Computer Science, 3850
   Google Scholar
• Gutiérrez-Naranjo , M. A. , Păun , Gh. and Pérez-Jiménez , M. J. , eds. 2005 . Cellular Computing. Complexity Aspects , Sevilla : Fenix Editora .
   Google Scholar
• Ibarra , O. H. 2005 . “ Some computational issues in membrane computing ” . In Proceedings of the 30th International Symposium, MFCS 2005 , 39 – 51 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 3618
   Google Scholar
• Ibarra , O. H. and Păun , G. 2006 . Characterizations of context-sensitive languages and other language classes in terms of symport/antiport P systems . Theor. Comput. Sci. , 358 : 88 – 103 .
   Google Scholar
• Ibarra , O. and Woodworth , S. 2006 . “ On bounded symport/antiport systems ” . In Pre-Proceedings of 11th International Meeting on DNA Computing 49 – 54 . Lecture Notes in Computer Science, 3850
   Google Scholar
• Ibarra , O. H. and Yen , H. C. 2006 . “ On deterministic catalytic P systems ” . In Proceedings of the CIAA05 , 164 – 176 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 3845
   Google Scholar
• Ibarra , O. H. , Yen , H.-C. and Dang , Z. 2005 . On various notions of parallelism in P systems . Int. J. Found. Comput. Sci. , 16 ( 4 ) : 683 – 705 .
   Google Scholar
• O. H. Ibarra et al., Normal forms for spiking neural P systems, Theor. Comput. Sci. 372 (2–3) (2007), pp. 196–217.
   Google Scholar
• Ibarra , O. H. 2006 . On the computational power of 1-deterministic and sequential P systems . Fund. Inform. , 73 ( 1–2 ) : 133 – 152 .
   Google Scholar
• Immerman , N. 1988 . Nondeterministic space is closed under complementation . SIAM J. Comput. , 17 ( 5 ) : 935 – 938 .
   Google Scholar
• Ionescu , M. , Păun , Gh. and Yokomori , T. 2006 . Spiking neural P systems . Fund. Inform. , 71 ( 2–3 ) : 279 – 308 .
   Google Scholar
• Ishdorj , T.-O. 2006 . “ Minimal parallelism for polarizationless P systems ” . 17 – 31 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 4287
   Google Scholar
• S. N. Krishna, Combining brane calculus and membrane computing, Submitted. (2006).
   Google Scholar
• Nishida , T. Y. 2004 . “ An application of P system: a new algorithm for NP-complete optimization problems ” . In Proceedings of the 8th World Multi-Conference on Systems, Cybernetics and Informatics Edited by: Callaos , N. Vol. V , 109 – 112 .
   Google Scholar
• Păun , Gh. 2000 . Computing with membranes . J. Comput. Syst. Sci. , 61 ( 1 ) : 108 – 143 . (and Turku Center for Computer Science – TUCS Report 208, November 1998, www.tucs.fi)
   Web of Science ®Google Scholar
• Păun , Gh. 2001 . P systems with active membranes: attacking NP-complete problems . J. Automata Lang. Comb. , 6 ( 1 ) : 75 – 90 .
   Google Scholar
• Păun , Gh. 2002 . Computing with Membranes: An Introduction , Berlin : Springer .
   Google Scholar
• Păun , A. and Păun , M. 2001 . “ On the membrane computing based on splicing ” . In Where Mathematics, Computer Science, Linguistics and Biology Meet , Edited by: Martin-Vide , C. and Mitrana , V. 409 – 422 . Dordrecht : Kluwer .
   Google Scholar
• Păun , A. and Păun , Gh. 2002 . The power of communication: P systems with symport/antiport . New Generat. Comput. , 20 ( 3 ) : 295 – 306 .
   Google Scholar
• Păun , A. and Popa , B. 2006 . P systems with proteins on membranes . Fund. Inform. , 72 ( 4 ) : 467 – 483 .
   Google Scholar
• Păun , A. and Popa , B. 2006 . “ P systems with proteins on membranes and membrane division ” . In Proc. of the Tenth International Conference on Developments in Language Theory (DLT) 292 – 303 . 26–29 June, Santa Barbara: CA
   Google Scholar
• Păun , Gh. , Pérez-Jiménez , M. J. and Rozenberg , G. 2006 . Spike trains in spiking neural P systems . Int. J. Found. Comput. Sci. , 17 ( 4 ) : 975 – 1002 .
   Google Scholar
• M. J. Pérez-Jiménez, and F. J. Romero-Campero, P systems, a new computational modeling tool for systems biology, Trans. Comput. Sys. Biol. 4 (2006), 176–197.
   Google Scholar
• Petreska , B. and Teuscher , C. 2004 . “ A hardware membrane system ” . In Membrane Computing. International Workshop, WMC2003, Tarragona, Spain, Revised Papers , Edited by: Martin-Vide , C. , Mauri , G. , Păun , Gh. , Rozenberg , G. and Salomaa , A. 269 – 285 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 2933
   Google Scholar
• A. Rodriguez-Paton and P. Sosik, Membrane computing and complexity theory: Characterization of PSPACE. J. Comput. Sys. Sci. 73(1) (2007), pp. 137–152.
   Google Scholar
• Romero-Campero , F. J. and Pérez-Jiménez , M. J. 2005 . “ A study of the robustness of the EGFR signalling cascade using continuous membrane systems ” . 268 – 278 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 3561
   Google Scholar
• Savitch , W. 1970 . Relationships between nondeterministic and deterministic tape complexities . J. Comput. Syst. Sci. , 4 ( 2 ) : 177 – 192 .
   Google Scholar
• Savitch , W. 1973 . A note on multihead automata and context-sensitive languages . Acta Inform. , 2 : 249 – 252 .
   Google Scholar
• Sosik , P. 2002 . “ P systems versus register machines: two universality proofs ” . In Pre-Proceedings of Workshop on Membrane Computing (WMC-CdeA Curtea de Arges, Romania 371 – 382 .
   Google Scholar
• Syropoulos , A. 2004 . “ A distributed simulation of P systems ” . In Membrane Computing. International Workshop, WMC2003, Tarragona, Spain, Revised Papers , Edited by: Martin-Vide , C. , Mauri , G. , Păun , Gh. , Rozenberg , G. and Salomaa , A. 355 – 366 . Berlin : Springer-Verlag . Lecture Notes in Computer Science, 2933
   Google Scholar
• Szelepcsényi , R. 1988 . The method of forced enumeration for nondeterministic automata . Acta Inform. , 26 ( 3 ) : 279 – 284 .
   Google Scholar
• The Web Page of Membrane Computing, http://psystems.disco.unimib.it .
   Google Scholar
• Zandron , C. , Ferretti , C. and Mauri , G. 2000 . “ Solving NP-complete problems using P systems with active membranes ” . In Unconventional Models of Computation , Edited by: Antoniou , I. , Calude , C. S. and Dinneen , M. J. 289 – 301 . London : Springer .
   Google Scholar