@article{Alhazov.etal:InflectionsRepl:CSJM2009, author = {Artiom Alhazov and Elena Boian and Svetlana Cojocaru and {\relax Yu}rii Rogozhin}, title = {Modelling Inflections in {R}omanian Language by {P} Systems with String Replication}, journal = {Computer Science Journal of Moldova}, volume = {17}, number = {2(50)}, year = {2009}, pages = {160-178}, bibdate = {07/12/10}, abstract = {The aim of this article is the formalization of inflection process for the Romanian language using the model of P systems with cooperative string replication rules, which will make it possible to automatically build the morphological lexicons as a base for different linguistic applications.}, url = {http://www.math.md/publications/csjm/issues/v17-n2/10082/}, } @article{Alhazov.etal:PDict:IJCCC2009, author = {Artiom Alhazov and Svetlana Cojocaru and Ludmila Malahova and {\relax Yu}rii Rogozhin}, title = {Dictionary Search and Update by {P} Systems with String-Objects and Active Membranes}, journal = {International Journal of Computers, Communications and Control}, volume = {IV}, number = {3}, year = {2009}, pages = {206-213}, bibdate = {07/12/10}, abstract = {Membrane computing is a formal framework of distributed parallel computing. In this paper we implement the work with the prefix tree by P systems with strings and active membranes. We present the algorithms of searching in a dictionary and updating it implemented as membrane systems. The systems are constructed as reusable modules, so they are suitable for using as sub-algorithms for solving more complicated problems.}, url = {http://www.journal.univagora.ro/?page=article_details&id=365}, } @article{Alhazov.etal:PartialPartitions:FI2009, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald and Sergey Verlan}, title = {Partial Halting and Minimal Parallelism Based on Arbitrary Rule Partitions}, journal = {Fundamenta Informaticae}, volume = {91}, number = {1}, year = {2009}, month = {April}, pages = {17-34}, bibdate = {07/12/10}, abstract = {We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems using membrane rules with permitting contexts and working in different transition modes, especially for minimal parallelism. Both partial halting and minimal parallelism are based on an arbitrary set of subsets from the set of rules assigned to the membranes.}, keywords = {computational completeness, halting, minimal parallelism, P systems, permitting context}, url = {http://dx.doi.org/10.3233/FI-2009-0031}, } @article{Alhazov.etal:tSAmincoo:IJFCS2007, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin and Sergey Verlan}, title = {Minimal Cooperation in Symport/Antiport Tissue {P}~Systems}, journal = {International Journal of Foundations of Computer Science}, volume = {18}, number = {1}, year = {2007}, month = {February}, pages = {163-180}, bibdate = {07/12/10}, abstract = {We investigate tissue P systems with symport/antiport with minimal cooperation, i.e., when only 2 objects may interact. We show that 2 cells are enough in order to generate all recursively enumerable sets of numbers. Moreover, constructed systems simulate register machines and have purely deterministic behavior. We also investigate systems with one cell and we show that they may generate only finite sets of numbers.}, url = {http://dx.doi.org/10.1142/S0129054107004619}, } @article{Ishdorj.etal:2010, author = {Tseren-Onolt Ishdorj and Alberto Leporati and Linqiang Pan and Xiangxiang Zeng and Xingyi Zhang}, title = {Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources}, journal = {Theoretical Computer Science}, bibdate = {01/22/10}, } @article{Pan.etal:2010c, author = { Linqiang Pan and Mario J. P{\'e}rez-Jim{\'e}nez}, title = {Computational Complexity of Tissue-like P Systems}, journal = {Journal of Complexity}, bibdate = {01/22/10}, } @article{Pan.etal:2010b, author = {Linqiang Pan and Gheorghe P\u{a}un}, title = {Spiking Neural P Systems: An Improved Normal Form}, journal = {Theoretical Computer Science}, volume = {411}, year = {2010}, pages = {906--918}, bibdate = {01/22/10}, } @article{Subramanian.etal:2009b, author = {K.G. Subramanian and Linqiang Pan and See Keong Lee and Atulya K. Nagar}, title = {P systems and context-free 2D picture languages}, journal = {Proceedings of the 4th BIC-TA}, year = {2009}, pages = {336--340}, bibdate = {01/22/10}, } @article{Zeng.etal:2009, author = {Xiangxiang Zeng and Chun Lu and Linqiang Pan}, title = {A weakly universal spiking neural P system}, journal = { Proceedings of the 4th BIC-TA}, year = {2009}, bibdate = {01/22/10}, } @article{Pan.etal:2010, author = {L. Pan and X. Zeng}, title = {A note on small universal spiking neural P systems}, journal = {Pre-proceedings of Tenth Workshop on Membrane Computing}, pages = {2009}, bibdate = {01/22/10}, } @article{Wang.etal:2009, author = { J. Wang and H.J. Hoogeboom and L. Pan and Gheorghe P\u{a}un}, title = {Spiking neural P systems with weights and thresholds}, journal = {Pre-proceedings of Tenth Workshop on Membrane Computing}, year = {2009}, bibdate = {01/22/10}, } @article{Pan.etal:2009, author = {Linqiang Pan and Gheorghe P\u{a}un}, title = {Spiking Neural P Systems with Anti-Spikes}, journal = {Int. J. of Computers, Communications {\&} Control}, volume = {4}, number = {3}, year = {2009}, pages = {273--282}, bibdate = {01/22/10}, } @article{Zhang.etal:2009b, author = {Xingyi Zhang and Xiangxiang Zeng and Linqiang Pan}, title = {On String Languages Generated by Asynchronous Spiking Neural P Systems}, journal = {Theoretical Computer Science}, volume = {410}, year = {2009}, pages = {2478--2488}, bibdate = {01/22/10}, } @article{Zhang.etal:2009, author = {Xingyi Zhang and Jun Wang and Linqiang Pan}, title = {A Note on the Generative Power of Axon P Systems}, journal = {International Journal of Computers, Communications {\&} Control}, volume = {4}, year = {2009}, pages = {92--98}, bibdate = {01/22/10}, } @article{Pan.etal:2008, author = {Linqiang Pan and Xingyi Zhang and Xiangxiang Zeng and Jun Wang}, title = {Research Advances and Prospect of Spiking Neural P Systems}, year = {2008}, journal = {Chinese Journal of Computers}, volume = {12}, pages = {2090--2096}, bibdate = {01/22/10}, } @article{Zhang.etal:2008e, author = {Xingyi Zhang and Xiangxiang Zeng and Linqiang Pan}, title = {Smaller Universal Spiking Neural P Systems}, journal = {Fundamenta Informaticae}, volume = {87}, number = {1}, year = {2008}, pages = {117--136}, bibdate = {01/22/10}, } @article{Zhang.etal:2008d, author = {Xingyi Zhang and Xiangxiang Zeng and Linqiang Pan}, title = {On string languages generated by spiking neural P systems with exhaustive use of rules}, journal = {Natural Computing}, volume = {7}, number = {4}, year = {2008}, pages = {535--549}, bibdate = {01/22/10}, } @article{Ciobanu.etal:2007b, author = {Gabriel Ciobanu and Linqiang Pan and Gheorghe P\u{a}un and Mario J.P{\'e}rez-Jim{\'e}nez}, title = {P systems with minimal parallelism}, journal = {Theoretic Computer Science}, volume = {378}, year = {2007}, pages = {117--130}, bibdate = {01/22/10}, } @article{Pan.Alhazov:HPPSAT:AI2006, author = { Linqiang Pan and Artiom Alhazov}, title = {Solving {HPP} and {SAT} by {P} Systems with Active Membranes and Separation Rules}, journal = {Acta Informatica}, volume = {43}, number = {2}, year = {2006}, pages = {131--145}, bibdate = {01/22/10}, abstract = {The P systems (or membrane systems) are a class of distributed parallel computing devices of a biochemical type, where membrane division is the frequently investigated way for obtaining an exponential working space in a linear time, and on this basis solving hard problems, typically NP-complete problems, in polynomial (often, linear) time. In this paper, using another way to obtain exponential working space - membrane separation, it was shown that Satisfiability Problem and Hamiltonian Path Problem can be deterministically solved in linear or polynomial time by a uniform family of P systems with separation rules, where separation rules are not changing labels, but polarizations are used. Some related open problems are mentioned.}, url = {http://dx.doi.org/10.1007/s00236-006-0018-8}, } @article{Pan.etal:2006, author = {Linqiang Pan and Carlos Mart{\'i}n-Vide}, title = {Further remark on P systems with active membranes and two polarizations}, journal = {Journal of Parallel and Distributed Computing}, volume = {66}, year = {2006}, pages = {867--872}, bibdate = {01/22/10}, } @article{Cazzaniga.etal:2008, author = {Paolo Cazzaniga and Dario Pescini and Daniela Besozzi and Giancarlo Mauri and Sonia Colombo and Enzo Martegani}, title = {Modeling and stochastic simulation of the Ras/cAMP/PKA pathway in the yeast Saccharomyces cerevisiae evidences a key regulatory function for intracellular guanine nucleotides pools}, journal = {Journal of Biotechnology}, volume = {133}, number = {3}, year = {2008}, pages = {377-385}, bibdate = {07/06/09}, } @article{Csuhaj-Varju.etal:2008b, author = {Erzs{\'e}bet Csuhaj-Varj{\'u} and Gheorghe P\u{a}un and Gy{\"o}rgy Vaszil}, title = {Tissue-like {P}~systems with dynamically emerging requests}, journal = {International Journal of Foundations of Computer Science}, year = {2008}, volume = {19}, number = {3}, pages = {729-745}, bibdate = {04/06/09}, } @article{Paun:2007, author = {Gheorghe P\u{a}un}, title = {Tracing some open problems in membrane computing}, journal = {Romanian Journal of Information Science and Technology}, year = {2007}, volume = {10}, number = {4}, pages = {303-314}, bibdate = {04/06/09}, } @article{Leporati.etal:toAppear, author = {Alberto Leporati and Daniela Besozzi and Paolo Cazzaniga and Claudio Ferretti and Dario Pescini}, title = {Computing with energy and chemical reactions}, journal = {Natural Computing}, year = {to appear}, bibdate = {04/06/09}, } @article{Gheorghe.etal:toAppear, author = {Marian Gheorghe and Vincenzo Manca and Francisco J. Romero-Campero}, title = {Deterministic and stochastic {P}~systems for modeling cellular processes}, journal = {Natural Computing}, bibdate = {04/06/09}, year = {to appear}, } @article{Kelemen:2008, author = {Jozef Kelemen}, title = {Some questions inspired by (membrane computing motivated) language-theoretic models hardware}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {571-580}, bibdate = {04/06/09}, } @article{Nguyen.etal:2008, author = {Van Nguyen and David Kearney and Gianpaolo Gioiosa}, title = {An implementation of membrane computing using reconfigurable hardware}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {551-569}, bibdate = {04/06/09}, } @article{Umeki.etal:2008, author = {Mai Umeki and Yasuhiro Suzuki}, title = {A Simple Membrane Computing Method for Simulating Bio-Chemical Reactions}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {515-528}, bibdate = {04/06/09}, } @article{Ionescu.etal:2008, author = {Mihai Ionescu and Drago\c{s} Sburlan}, title = {Some applications of spiking neural {P}~systems}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {515-528}, bibdate = {04/06/09}, } @article{Cordona.etal:2008, author = {M{\'o}nica Cordona and M. Angels Colomer and Mario J. P{\'e}rez Jim{\'e}nez and Alba Zaragoza}, title = {Hierarchical Clustering with Membrane Computing}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {497-513}, bibdate = {04/06/09}, } @article{Cienciala.etal:2008, author = {Lud\v{e}k Cienciala and Lucie Ciencialov{\'a} and Alice Kelemenov{\'a}}, title = {Homogeneous P Colonies}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {481-496}, bibdate = {04/06/09}, } @article{Molteni.etal:2008, author = {Davide Molteni and Claudio Ferretti and Giancarlo Mauri}, title = {Frequency Membrane Systems}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {467-479}, bibdate = {04/06/09}, } @article{Ramesh.etal:2008, author = {H. Ramesh and Raghavan Rama}, title = {Rewriting {P}~Systems with Conditional Communication: Improved Hierarchies}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {453-465}, bibdate = {04/06/09}, } @article{Bonchis.etal:2008, author = {Cosmin Bonchi\c{s} and Cornel Izba\c{s}a and Gabriel Ciobanu}, title = {Information Theory over Multisets}, journal = {Computing and Informatics}, year = {2008}, volume = {27}, number = {3+}, pages = {441-451}, bibdate = {04/06/09}, } @article{Manca:2008, author = {Vincenzo Manca}, title = {The metabolic algorithm for {P}~systems: Principles and applications}, journal = {Theoretical Computer Science}, year = {2008}, volume = {404}, number = {1-2}, pages = {142-155}, bibdate = {04/06/09}, } @article{Csuhaj-Varju.etal:2008, author = {Erzs{\'e}bet Csuhaj-Varj{\'u} and Gy\"orgy Vaszil}, title = {(Mem)brane automata}, journal = {Theoretical Computer Science}, year = {2008}, volume = {404}, number = {1-2}, pages = {52-60}, bibdate = {04/06/09}, } @article{Jack.etal:2008, author = {John Jack and Alfonso Rodr{\'i}guez-Pat{\'o}n and Oscar H. Ibarra and Andrei P\u{a}un}, title = {Discrete nondeterministic modeling of the {F}as pathway}, journal = {International Journal of Foundations of Computer Science}, year = {2008}, volume = {19}, number = {5}, pages = {1147-1162}, bibdate = {04/06/09}, } @article{Kari.etal:2008, author = {Lila Kari and Grzegorz Rozenberg}, title = {The many facets of natural computing}, journal = {Communications of the ACM}, year = {2008}, volume = {51}, number = {10}, pages = {72-83}, bibdate = {04/06/09}, } @article{Barbuti.etal:2008c, author = {Roberto Barbuti and Andrea Maggiolo-Schettini and Paolo Milazzo and Angelo Troina}, title = {Bisimulations in calculi modelling membranes}, journal = {Formal Aspects of Computing}, year = {2008}, volume = {20}, number = {4-5}, pages = {351-377}, bibdate = {04/06/09}, } @article{Kleijn.etal:toAppear, author = {Jetty Kleijn and Maciej Koutny}, title = {A {P}etri net model for membrane systems with dynamic structure}, journal = {Natural Computing}, bibdate = {04/06/09}, year = {to appear}, } @article{Kleijn.etal:2008, author = {Jetty Kleijn and Maciej Koutny}, title = {Processes of membrane systems with promoters and inhibitors}, journal = {Theoretical Computer Science}, year = {2008}, volume = {404}, number = {1-2}, pages = {112-126}, bibdate = {04/06/09}, } @article{Dovier.etal:2008, author = {Agostino Dovier and Carla Piazza and Gianfranco Rossi}, title = {A uniform approach to constraint-solving for lists multisets, compact lists, and sets}, journal = {ACM Transactions on Computational Logic}, year = {2008}, volume = {9}, number = {3}, pages = {15:1-15:30}, bibdate = {04/06/09}, } @article{Castellini.etal:toAppear, author = {Alberto Castellini and Giuditta Franco and Vincenzo Manca}, title = {Hybrid Functional {P}etri Nets as {MP} systems}, journal = {Natural Computing}, year = {to appear}, bibdate = {04/06/09}, } @article{Huang.etal:2008, author = {Chunyi Huang and Xiaoju Dong}, title = {Maximally parallel attribute on {P}~Systems: Properties and applications}, journal = {Progress in Natural Science}, year = {2008}, volume = {18}, number = {5}, pages = {629-632}, bibdate = {04/06/09}, } @article{Brijder.etal:2008, author = {Robert Brijder and Matteo Cavaliere and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Grzegorz Rozenberg and Drago\c{s}, Sburlan}, title = {Membrane systems with proteins embedded in membranes}, journal = {Theoretical Computer Science}, year = 2008, volume = 404, number = {1-2}, pages = {26-39}, bibdate = {04/06/09}, } @article{Martinez.etal:2007, author = {Victor Martinez and Luis Fernandez and Fernando Arroyo and Abraham Gutierrez}, title = {{HW} implementation of a optimized algorithm for the application of active rules in a transition {P}-system}, journal = {International Journal on Information Theory and Applications}, year = {2007}, volume = {14}, number = {4}, pages = {324-331}, bibdate = {04/06/09}, } @article{Cavaliere.etal:2008b, author = {Matteo Cavaliere and Radu Mardare and Sean Sedwards}, title = {A multiset-based model of synchronizing agents: Computability and robustness}, journal = {Theoretical Computer Science}, year = {2008}, volume = {391}, number = {3}, pages = {216-238}, bibdate = {04/06/09}, } @article{Ishdorj.etal:2008, author = {Tseren-Onolt Ishdorj and Alberto Leporati}, title = {Uniform solutions to {SAT} and {3-SAT} by spiking neural {P}, systems with pre-computed resources}, journal = {Natural Computing}, year = {2008}, volume = {7}, number = {4}, pages = {519-534}, bibdate = {04/06/09}, } @article{Romero-Campero.etal:2008b, author = {Francisco J. Romero-Campero and Mario J. P{\'e}rez-Jim{\'e}nez}, title = {A model of the quorum sensing system in {V}ibrio fischeri using {P}~systems}, journal = {Artificial Life}, year = {2008}, volume = {14}, number = {1}, pages = {95-109}, bibdate = {04/06/09}, } @article{Cavaliere.etal:2008, author = {Matteo Cavaliere and Ivan Mura}, title = {Experiments on the reliability of stochastic spiking neural {P}~systems}, journal = {Natural Computing}, year = {2008}, volume = {7}, number = {4}, pages = {453-470}, bibdate = {04/06/09}, } @article{Huang.etal:2009, author = {Liang Huang and Il Hong Suh}, title = {Controller design for a marine diesel engine using membrane computing}, journal = {International Journal of Innovative Computing, Information and Control}, year = {2009}, volume = {5}, number = {4}, pages = {899-912}, bibdate = {04/06/09}, } @article{Huang.etal:2007, author = {Liang Huang and Lei Sun and Ning Wang and Xiaoming Jin}, title = {Multiobjective optimization of simulated moving bed by tissue {P}~system}, journal = {Chinese Journal of Chemical Engineering}, year = {2007}, volume = {15}, number = {5}, pages = {683-690}, bibdate = {04/06/09}, } @article{Freund.etal:2008b, author = {Rudolf Freund and Marion Oswald}, title = {Regular omega-languages defined by finite extended spiking neural {P}~systems}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {83}, number = {1-2}, pages = {65-73}, bibdate = {04/06/09}, } @article{Alhazov:Ciliate:ROMJIST2008, author = {Artiom Alhazov}, title = {Ciliate Operations without Context in a Membrane Computing Framework}, journal = {Romanian Journal of Information Science and Technology}, year = {2008}, volume = {10}, number = {4}, pages = {315--322}, bibdate = {04/06/09}, abstract = {We study the computational power of string processing systems with excision and insertion rules with communication. The strings are distributed in different regions, and the rules are defined by cutting out a substring flanked by specific repeated symbols and a reverse operation; the rule only specifies the repeated symbol and the regions of reactants and products. It turns out that they can generate all recursively enumerable sets of non-negative integers.}, url = {http://www.imt.ro/romjist/Volum10/Number10_4/02-Alhazov.htm}, } @article{Nishida:2007, author = {Taishin Y. Nishida}, title = {Membrane algorithm with brownian subalgorithm and genetic subalgorithm}, journal = {International Journal of Foundations of Computer Science}, year = {2007}, volume = {18}, number = {6}, pages = {1353-1360}, bibdate = {04/06/09}, } @article{Ibarra.etal:2007b, author = {Oscar H. Ibarra and Sara Woodworth}, title = {Characterizing regular languages by spiking neural {P}~systems}, journal = {International Journal of Foundations of Computer Science}, year = {2007}, volume = {18}, number = {6}, pages = {1247-1256}, bibdate = {04/06/09}, } @article{Gao.etal:2007, author = {Yan Gao and Hendrik Jan Hoogeboom}, title = {{P}~systems with single passenger carriers}, journal = {International Journal of Foundations of Computer Science}, year = {2007}, volume = {18}, number = {6}, pages = {1227-1235}, bibdate = {04/06/09}, } @article{Freund.etal:2008, author = {Rudolf Freund and Mihai Ionescu and Marion Oswald}, title = {Extended spiking neural {P}~systems with decaying spikes and/or total spiking}, journal = {International Journal of Foundations of Computer Science}, year = {2008}, volume = {19}, number = {5}, pages = {1223-1234}, bibdate = {04/06/09}, } @article{Bernardini.etal:2008, author = {Francesco Bernardini and Marian Gheorghe and Maurice Margenstern and Sergey Verlan}, title = {How to synchronize the activity of all components of a {P}~system?}, journal = {International Journal of Foundations of Computer Science}, year = {2008}, volume = {19}, number = {5}, pages = {1183-1198}, bibdate = {04/06/09}, } @article{Annadurai.etal:2008b, author = {Subbaiah Annadurai and Thiyagarajan Kalyani and Vincent Rajkumar Dare and Durairaj Gnanaraj Thomas}, title = {Trajectory {P}~systems}, journal = {Progress in Natural Science}, year = {2008}, volume = {18}, number = {5}, pages = {611-616}, bibdate = {04/06/09}, } @article{Annadurai.etal:2008, author = {Subbaiah Annadurai and Thiyagarajan Kalyani and Vincent Rajkumar Dare and Durairaj Gnanaraj Thomas}, title = {{P}~systems generating iso-picture languages}, journal = {Progress in Natural Science}, year = {2008}, volume = {18}, number = {5}, pages = {617-622}, bibdate = {04/06/09}, } @article{Xian:2007, author = {Xu Xian}, title = {Tissue {P}~systems with parallel rules on channels}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {486-491}, bibdate = {04/06/09}, } @article{Subramanian.etal:2007, author = {K. G. Subramanian and R. Saravanan and M. Geethalakshmr and P. Helen Chandra and M. Margenstern}, title = {{P}~systems with array objects and array rewriting rules}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {479-485}, bibdate = {04/06/09}, } @article{Leporati.etal:2007b, author = {Alberto Leporati and Claudio Zandron and Giancarlo Mauri}, title = {Solving the factorization problem with {P}~systems}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {471-478}, bibdate = {04/06/09}, } @article{Korczynski:2007, author = {Waldemar Korczynski}, title = {Paun's systems as models of economic systems}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {466-470}, bibdate = {04/06/09}, } @article{Liang.etal:2007, author = {Huang Liang and He Xiongxiong and Wang Ning and Xie Yi}, title = {{P}~systems based multi-objective optimization algorithm}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {458-465}, bibdate = {04/06/09}, } @article{Gutierrez-Naranjo.etal:2007b, author = {Miguel A. Guti{\'e}rrez-Naranjo and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Francisco J. Romero-Campero}, title = {How to express tumours using membrane systems}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {449-457}, bibdate = {04/06/09}, } @article{Freund.etal:2007b, author = {Rudolf Freund and Marion Oswald and Thomas Schirk}, title = {How a membrane agent buys goods in a membrane store}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {442-448}, bibdate = {04/06/09}, } @article{Ciobanu.etal:2007, author = {Gabriel Ciobanu and Laura Cornacel}, title = {Probabilistic transitions for {P}~systems}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {431-441}, bibdate = {04/06/09}, } @article{Cheruku.etal:2007, author = {Smitha Cheruku and Andrei P\u{a}un and Francisco J. Romero-Campero and Mario J. P{\'e}rez-Jim{\'e}nez and Oscar H. Ibarra}, title = {Simulating {FAS}-induced apoptosis by using {P}~systems}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {424-431}, bibdate = {04/06/09}, } @article{Haiming.etal:2007, author = {Chen Haiming and Tseren-Onolt Ishdorj and Gheorghe P\u{a}un}, title = {Computing along the axon}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {417-423}, bibdate = {04/06/09}, } @article{Bonchis.etal:2007, author = {Cosmin Bonchis and Cornel Izbasa and Gabriel Ciobanu}, title = {Compositional asynchronous membrane systems}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {411-416}, bibdate = {04/06/09}, } @article{Binder.etal:2007, author = {Aneta Binder and Rudolf Freund and Georg Lojka and Marion Oswald}, title = {Applications of membrane systems in distributed systems}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {401-409}, bibdate = {04/06/09}, } @article{Besozzi.etal:2007, author = {Daniela Besozzi and Paolo Cazzaniga and Dario Pescini and Giancarlo Mauri}, title = {Seasonal variance in {P}~system models for metapopulations}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {392-400}, bibdate = {04/06/09}, } @article{Manca:2007, author = {Vincenzo Manca}, title = {Metabolic {P}~systems for biochemical dynamics}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {384-391}, bibdate = {04/06/09}, } @article{Romero-Campero.etal:2007, author = {Francisco J. Romero-Campero and Marian Gheorghe and Gabriel Ciobanu and John M. Auld and Mario J. P{\'e}rez-Jim{\'e}nez}, title = {Cellular modelling using {P}~systems and process algebra}, journal = {Progress in Natural Science}, year = {2007}, volume = {17}, number = {4}, pages = {375-383}, bibdate = {04/06/09}, } @article{Yang.etal:2008, author = {Linmin Yang and Zhe Dang and Oscar H. Ibarra}, title = {On stateless automata and {P}~systems}, journal = {Intenational Journal of Foundations of Computer Science}, year = {2008}, volume = {19}, number = {5}, pages = {1259-1276}, bibdate = {04/06/09}, } @article{Mardare.etal:2008, author = {Radu Mardare and Matteo Cavaliere and Sean Sedwards}, title = {A logical characterization of robustness, mutants and species in colonies of agents}, journal = {Intenational Journal of Foundations of Computer Science}, year = {2008}, volume = {19}, number = {5}, pages = {1199-1221}, bibdate = {04/06/09}, } @article{Vitale.etal:2008, author = {Antonio Vitale and Giancarlo Mauri and Claudio Zandron}, title = {Simulation of a bounded symport/antiport {P}~system with {B}rane calculi}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {558-571}, bibdate = {04/06/09}, } @article{Fontana.etal:2008, author = {Federico Fontana and Vincenzo Manca}, title = {Predator-prey dynamics in {P}~systems ruled by metabolic algorithm}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {545-557}, bibdate = {04/06/09}, } @article{Corne.etal:2008, author = {David W. Corne and Pierluigi Frisco}, title = {Dynamics of {HIV} infection studied with cellular automata and conformon-{P} systems}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {531-544}, bibdate = {04/06/09}, } @article{Ciobanu.etal:2008b, author = {Gabriel Ciobanu and Bogdan Aman}, title = {On the relationship between membranes and ambients}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {515-530}, bibdate = {04/06/09}, } @article{Besozzi.etal:2008, author = {Daniela Besozzi and Paolo Cazzaniga and Dario Pescini and Giancarlo Mauri}, title = {Modelling metapopulations with stochastic membrane systems}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {499-514}, bibdate = {04/06/09}, } @article{Manca.etal:2008, author = {Vincenzo Manca and Luca Bianco}, title = {Biological networks in metabolic {P}~systems}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {489-498}, bibdate = {04/06/09}, } @article{Franco.etal:2008, author = {Giuditta Franco and Nata\v{s}a Jonoska and Barbara Osborn and Anna Plaas}, title = {Knee joint injury and repair modeled by membrane systems}, journal = {Biosystems}, year = 2008, volume = 91, number = 3, pages = {473-488}, bibdate = {04/06/09}, } @article{Spicher.etal:2008, author = {Antoine Spicher and Olivier Michel and Mikolaj Cieslak and Jean-Louis Giavitto and Przemyslaw Prusinkiewicz}, title = {Stochastic {P}~systems and the simulation of biochemical processes with dynamic compartments}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {458-472}, bibdate = {04/06/09}, } @article{Romero-Campero.etal:2008, author = {Francisco J. Romero-Campero and Mario J. P{\'e}rez-Jim{\'e}nez}, title = {Modelling gene expression control using {P}~systems: The {L}ac {O}peron, a case study}, journal = {Biosystems}, year = {2008}, volume = {91}, number = {3}, pages = {438-457}, bibdate = {04/06/09}, } @article{Gheorghe.etal:2008, author = {Marian Gheorghe and Natalio Krasnogor and Miguel Camara}, title = {{P}~systems applications to systems biology}, journal = {Biosystems}, year = 2008, volume = 91, number = 3, pages = {435-437}, bibdate = {04/06/09}, } @article{Zhang.etal:2008b, author = {Xingyi Zhang and Xiangxiang Zeng and Linqiang Pan}, title = {Smaller Universal Spiking Neural {P}~Systems}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {87}, number = {1}, pages = {117-136}, bibdate = {04/06/09}, } @article{Zhang.etal:2008, author = {Ge-Xiang Zhang and Marian Gheorghe and Chao-Zhong Wu}, title = {A Quantum-Inspired Evolutionary Algorithm Based on {P}~systems for Knapsack Problem}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {87}, number = {1}, pages = {93-116}, bibdate = {04/06/09}, } @article{Zandron.etal:2008, author = {Claudio Zandron and Alberto Leporati and Claudio Ferretti and Giancarlo Mauri and Mario J. P{\'e}rez-Jim{\'e}nez }, title = {On the Computational Efficiency of Polarizationless Recognizer {P}~Systems with Strong Division and Dissolution}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {87}, number = {1}, pages = {79-91}, bibdate = {04/06/09}, } @article{Leporati.etal:2008, author = {Alberto Leporati and Miguel A. Guti{\'e}rrez-Naranjo}, title = {Solving Subset Sum by Spiking Neural {P}~Systems with Pre-computed Resources}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {87}, number = {1}, pages = {61-77}, bibdate = {04/06/09}, } @article{Ciobanu.etal:2008, author = {Gabriel Ciobanu and Andreas Resios}, title = {Computational Complexity of Simple {P}~Systems}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {87}, number = {1}, pages = {49-59}, bibdate = {04/06/09}, } @article{Ceterchi.etal:2008, author = {Rodica Ceterchi and Alexandru Ioan Tomescu}, title = {Implementing Sorting Networks with Spiking Neural {P}~Systems}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {87}, number = {1}, pages = {35-48}, bibdate = {04/06/09}, } @article{Barbuti.etal:2008b, author = {Roberto Barbuti and Andrea Maggiolo-Schettini and Paolo Milazzo and Simone Tini}, title = {A {P} Systems Flat Form Preserving Step-by-step Behaviour}, journal = {Fundamenta Informaticae}, year = {2008}, volume = {87}, number = {1}, pages = {1-34}, bibdate = {04/06/09}, } @article{Muskulus.etal:2007, author = {Michael Muskulus and Daniela Besozzi and Robert Brijder and Paolo Cazzaniga and Sanne Houweling and Dario Pescini and Grzegorz Rozenberg}, title = {Cycles and communicating classes in membrane systems and molecular dynamics}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, bibdate = {04/06/09}, } @article{Leporati.etal:2007, author = {Alberto Leporati and Sara Felloni}, title = {Three ``quantum'' algorithms to solve {3-SAT}}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, pages = {218-241}, bibdate = {04/06/09}, } @article{Ibarra.etal:2007, author = {Oscar H. Ibarra and Andrei P\u{a}un and Gheorghe P\u{a}un and Alfonso Rodr{\'i}guez-Pat{\'o}n and Petr Sos{\'i}k and Sara Woodworth}, title = {Normal forms for spiking neural {P}~systems}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, pages = {196-217}, bibdate = {04/06/09}, } @article{Gutierrez-Naranjo.etal:2007, author = {Miguel A. Guti{\'e}rrez-Naranjo and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'i}n Riscos-N{\'u}{\~n}ez}, title = {On the degree of parallelism in membrane systems}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, pages = {183-195}, bibdate = {04/06/09}, } @article{Fontana.etal:2007, author = {Federico Fontana and Vincenzo Manca}, title = {Discrete solutions to differential equations by metabolic P systems}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, pages = {165-182}, bibdate = {04/06/09}, } @article{Csuhaj-Varju.etal:2007, author = {Erzs{\'e}bet Csuhaj-Varj{\'u} and Maurice Margenstern and Gy\"orgy Vaszil and Sergey Verlan}, title = {On small universal antiport {P}~systems}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, pages = {152-164}, bibdate = {04/06/09}, } @article{Cavaliere.etal:2007, author = {Matteo Cavaliere and Rudolf Freund and Marion Oswald and Drago\c{s} Sburlan}, title = {Multiset random context grammars, checkers, and transducers}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, pages = {136-151}, bibdate = {04/06/09}, } @article{Busi:2007, author = {Nadia Busi}, title = {Using well-structured transition systems to decide divergence for catalytic {P}~systems}, journal = {Theoretical Computer Science}, year = {2007}, volume = {372}, number = {2-3}, pages = {125-135}, bibdate = {04/06/09}, } @article{Barbuti.etal:2008, author = {Roberto Barbuti and Andrea Maggiolo-Schettini and Paolo Milazzo and Simone Tini}, title = {Compositional semantics and behavioral equivalences for {P}~Systems}, journal = {Theoretical Computer Science}, year = {2008}, volume = {395}, number = {1}, pages = {77-100}, bibdate = {04/06/09}, } @article{Krishna:2007, author = {Shankara N. Krishna}, title = {Universality results for {P}~systems based on brane calculi operations}, journal = {Theoretical Computer Science}, year = {2007}, volume = {371}, number = {1-2}, pages = {83-105}, bibdate = {04/06/09}, } @article{Gutierrez-Naranjo.etal:2006, author = {Miguel A. Guti{\'e}rrez-Naranjo and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Francisco J. Romero-Campero}, title = {Computational efficiency of dissolution rules in membrane systems}, journal = {International Journal of Computer Mathematics}, year = {2006}, volume = {83}, number = {7}, pages = {593-611}, bibdate = {04/06/09}, } @article{Bianco.etal:2006, author = {Luca Bianco and Vincenzo Manca}, title = {Symbolic generation and representation of complex oscillations}, journal = {International Journal of Computer Mathematics}, year = {2006}, volume = {83}, number = {7}, pages = {549-568}, bibdate = {04/06/09}, } @article{Nagy.etal:2006, author = {Benedek Nagy and Laszlo Szegedi}, title = {Membrane computing and geographical operating systems}, journal = {Journal of Universal Computer Science}, year = {2006}, volume = {12}, number = {9}, pages = {1312-1331}, bibdate = {04/06/09}, } @article{Alhazov.Rogozhin:SALang:CSJM2006, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin}, title = {Generating Languages by {P}~Systems with Minimal Symport/Antiport}, journal = {The Computer Science Journal of Moldova}, year = {2006}, volume = {14}, number = {3}, pages = {299--323}, bibdate = {04/06/09}, abstract = {It is known that P systems with two membranes and minimal symport/antiport rules are ``almost'' computationally complete as generators of number or vector sets. Interpreting the result of the computation as the sequence of terminal symbols sent to the environment, we show that P systems with two membranes and symport rules of weight two or symport/antiport rules of weight one generate all recursively enumerable languages.}, url = {http://www.math.md/publications/csjm/issues/v14-n3/8609/}, } @article{Freund.etal:2007, author = {Rudolf Freund and Marion Oswald}, title = {Partial halting in {P}~systems}, journal = {International Journal of Foundations of Computer Science}, year = {2007}, volume = {18}, number = {6}, pages = {1215-1225}, bibdate = {04/06/09}, } @article{Sosik.etal:2007, author = {Petr Sos{\'i}k and Alfonso Rodr{\'i}guez-Pat{\'o}n}, title = {Membrane computing and complexity theory: A characterization of {PSPACE}}, journal = {Journal of Computer and System Sciences}, year = {2007}, volume = {73}, number = {1}, pages = {137-152}, bibdate = {04/06/09}, } @article{Verlan.etal:2008b, author = {Sergey Verlan and Francesco Bernardini and Marian Gheorghe and Maurice Margenstern}, title = {Generalized communicating {P}~systems}, journal = {Theoretical Computer Science}, year = {2008}, volume = {404}, number = {1-2}, pages = {170-184}, bibdate = {04/06/09}, } @article{Subramanian.etal:2009, author = {K. G. Subramanian and Rosihan M. Ali and Atulya K. Nagar and Maurice Margenstern}, title = {Array {P} Systems and t-Communication}, journal = {Fundamenta Informaticae}, year = {2009}, volume = {91}, number = {1}, pages = {145-159}, bibdate = {04/06/09}, } @article{Zhang:2009, author = {Zhang, Yao; Huang, Liang}, title = {A variant of P systems for optimization}, journal = {NEUROCOMPUTING}, volume = {72}, number = {4-6}, year = {2009}, pages = {1355-1360}, bibdate = {03/11/09}, } @article{Sosik:The_power_of_ca:02, author = {Petr Sos{\'i}k}, title = {The power of catalysts and priorities in membranes}, journal = {Grammars}, year = {2003}, volume = {6}, pages = {13--24}, } @article{Alhazov.etal:DivCreaOC:IJCM2006, author = {Artiom Alhazov and Rudolf Freund and Agust{\'\i}n Riscos-N{\'u}{\~n}ez}, title = {Membrane Division, Restricted Membrane Creation and Object Complexity in {P}~Systems}, journal = {International Journal of Computer Mathematics}, volume = {83}, number = {7}, year = {2006}, pages = {529--548}, abstract = {We improve, by using register machines, some existing universality results for specific models of P systems. P systems with membrane creation are known to generate all recursively enumerable sets of vectors of non-negative integers, even when no region (except the environment) contains more than one object of the same kind. We show here that they generate all recursively enumerable languages, and that two membrane labels are sufficient (the same result holds for accepting all recursively enumerable vectors of non-negative integers). Moreover, at most two objects are present inside the system at any time in the generative case. We then prove that 10+m symbols are sufficient to generate any recursively enumerable language over m symbols. P systems with active membranes without polarizations are known to generate all recursively enumerable sets of vectors of non-negative integers. We show that they generate all recursively enumerable languages; four starting membranes with three labels or seven starting membranes with two labels are sufficient. P systems with active membranes and two polarizations are known to generate/accept all recursively enumerable sets of vectors of non-negative integers, using only rules of rewriting and sending objects out. We show that accepting can be done by deterministic systems. Finally, we show that P systems with restricted membrane creation (the newly created membrane can only be of the same kind as the parent one) generate at least matrix languages, even when having at most one object in the configuration (except the environment). We conclude by presenting a summary of the main results obtained in this paper and a list of open questions.}, keywords = {Membrane division, Restricted membrane creation, Object complexity, P systems}, url = {http://dx.doi.org/10.1080/00207160601065314}, } @article{RomPer:AModel:2008, author = {F.J. Romero-Campero and M.J. Perez-Jimenez}, title = {A model of the quorum sensing system in Vibrio fischeri}, journal = {Artificial Life}, volume = {14}, number = {1}, year = {2008}, pages = {95-109}, bibdate = {03/03/08}, } @article{Paun:Tracing:2007, author = {Gh. Paun}, title = {Tracing some open problems in membrane computing}, journal = {ROMJIST}, volume = {10}, number = {4}, year = {2007}, pages = {303-314}, bibdate = {02/22/08}, } @article{PauPer:SpikRecent:2008, author = {Gh. Paun and M.J. Perez-Jimenez}, title = {Spiking neural P systems. Recent results, research topics}, journal = {submitted}, year = {2008}, bibdate = {02/22/08}, } @article{Cavaliere:Experiments:2008, author = {M. Cavaliere and I. Mura}, title = {Experiments on the reliability of stochastic spiking neural P systems}, journal = {Natural Computing}, volume = {to appear}, year = {2008}, bibdate = {02/13/08}, } @article{Krishna:Onthecomp:2008, author = {S.N. and G. Ciobanu}, title = {On the computational power of enhanced mobile membranes}, journal = {submitted}, year = {2008}, bibdate = {02/13/08}, } @article{Metta:Spiking:2008, author = {V.P. Metta and K. Krithivasan}, title = {Spiking Neural P systems and Petri nets}, journal = {submitted}, year = {2008}, bibdate = {02/13/08}, } @article{GarciaArnau:Onthepower:2008, author = {M. Garcia-Arnau and D. Perez and A. Rodriguez-Paton and P. Sosik}, title = {On the power of elementary operations in spiking neural P systems}, journal = {Natural Computing}, volume = {to appear}, year = {2008}, bibdate = {02/13/08}, } @article{M.Garcia-Arnau:2007, author = {M. Garcia-Arnau and D. Manrique and A. Rodriguez-Paton and P. Sosik}, title = {A P system and a constructive membrane-inspired DNA algorithm for solving the Maximum Clique Problem}, journal = {BioSystems}, volume = {90}, number = {3}, year = {2007}, pages = {687-697}, bibdate = {02/13/08}, } @article{Huang:2008b, author = {L. Huang and N. Wang}, title = {A variant of P systems for optimization}, journal = {Neurocomputing}, volume = {to appear}, bibdate = {02/13/08}, } @article{Teuscher:BioSystems:ToAppear, author = {C. Teuscher}, title = {From membranes to systems: self-configuration and self-replication in membrane systems}, journal = {BioSystems}, note = {To appear (IPCAT 2005)}, } @article{Franco:Knee_joint_injury:, author={G. Franco and N. Jonoska and B. Osborn and A. Plaas}, title={Knee joint injury and repair modeled by membrane systems}, journal={Biosystems}, note={To appear} } @article{Paun:MembraneComputingQuick, author = {Gh. Paun}, title = {A quick overview of membrane computing with some details about spiking neural {P} systems}, journal = {Frontiers of Computer Science in China}, note = {To appear}, } @article{PaunPaun:MembraneEconomics, author={Gh. Paun and R. Paun}, title={Membrane computing models for economics. {A}n invitation-survey}, journal={Studii \c si Cercet\u ari de Calcul Economic si Cibernetica Economica}, note={To appear} } @article{Muskulus:Cycles_and:, author={M. Muskulus and D. Besozzi and R. Brijder and P. Cazzaniga and S. Houweling and D. Pescini and G. Rozenberg}, title={Cycles and communicating classes in membrane systems and molecular dynamics}, journal={Theoretical Computer Science}, note={To appear} } @article{Muskulus:IJFCS:ToAppear, author={M. Muskulus and R. Brijder}, title={Complexity of biocomputation: symbolic dynamics in membrane systems}, journal={Intern. J. Found. Computer Sci.}, note={To Appear} } @article{Paun:BEATCS:Computing_with_Correction:99, author={Gheorghe P{\u a}un}, title={Computing with Membranes. {A} Correction. {T}wo Problems and Some Bibliographical Remarks}, journal={Bulletin of the EATCS}, year={1999}, month={October}, number={69}, pages={141--144} } @article{Paun:BEATCS:Computing_with_M_Intro:99, author={Gheorghe P{\u a}un}, title={Computing with Membranes. {A}n Introduction}, journal={Bulletin of the EATCS}, year={1999}, month={February}, number={67}, pages={139--152} } @article{Paun:FUND_INFORM:On_Synchronizat:99, author={Gheorghe P{\u a}un and Sheng Yu}, title={On Synchronization in {P} systems}, journal={Fundamenta Informaticae}, year={1999}, month={June}, volume={38}, number={4}, pages={397--410} } @article{Petre:BEATCS:A_Normal_Form_f:99, author={Ion Petre}, title={A Normal Form for {P} systems}, journal={Bulletin of the EATCS}, year={1999}, month={February}, number={67}, pages={165--172} } @article{Petre:J_UNIVERS_COMPUT_SCI:Mobile_Ambients:99, author={Ion Petre and Luigia Petre}, title={Mobile Ambients and {P} systems}, journal={Journal of Universal Computer Science}, year={1999}, volume={5}, number={9}, pages={588--598}, abstract={The ambient calculus and the P-systems are models developed in different areas of computer science. Still, they are based on similar concepts and structures and are inspired from the same natural model of computation [BeBo92]. On this basis, we point out how to transfer ideas and results from one framework to the other. We prove that any P-system can be simulated in ambient calculus. We also introduce the notion of mobile P-systems, suitable to model and motivate security features for membrane computing.} } @article{Dassow:J_UNIVERS_COMPUT_SCI:On_the_Power_of:99, author={J{\"u}rgen Dassow and Gheorghe P{\u a}un}, title={On the Power of Membrane Computing}, journal={Journal of Universal Computer Science}, year={1999}, volume={5}, number={2}, pages={33--49}, abstract={We continue the investigation of the power of the computability models introduced in [12] under the name of transition super-cell systems. We compare these systems with classic mechanisms in formal language theory, context-free and matrix grammars, E0L and ET0L systems, interpreted as generating mechanisms of number relations (we take the Parikh image of the usual language generated by these mecha- nisms rather than the language). Several open problems are also formulated.} } @article{Freund:Grammars:Generalized_P_S:99, author={Rudolf Freund}, title={Generalized {P} systems with Splicing and Cutting/Recombination}, journal={Grammars}, year={1999}, month={December}, volume={2}, number={3}, pages={189--199}, abstract={P-systems recently were introduced by Gheorghe Paun as a new model for computations based on membrane structures. Using the membranes as a kind of filter for specific objects when transferring them into an inner compartment turned out to be a very powerful mechanism in combination with suitable rules to be applied within the membranes in the model of generalized P-systems, GP-systems for short. In general, GP-systems allow for the simulation of graph controlled grammars of arbitrary type based on productions working on single objects. In this paper we consider GP-systems as computing devices using splicing or cutting and recombination of strings. Various variants of such systems are proved to have universal computational power, e.g., we show how test tube systems based on splicing or cutting and recombination of strings can be simulated by the corresponding GP-systems.} } @article{Krishna:ROMJIST:A_Variant_of_P_:99, author={Shankara Narayanan Krishna and Raghavan Rama}, title={A Variant of {P} systems with Active Membranes: Solving {NP-Complete} Problems}, journal={Romanian Journal of Information Science and Technology}, year={1999}, volume={2}, number={4}, pages={357--367}, abstract={A new class of distributed computing models inspired from biology, that of P systems, was recently introduced by Gh. Paun. Several variants of P systems were already shown to be computationally universal, equal in power to Turing Machines. In this paper, we propose a class of P systems with active membranes where a membrane can be divided into an arbitrary (but finite) number of membranes. We prove that this variant is able to solve NP-complete problems in polynomial (in fact, linear) time. We exemplify this assertion with the well known Hamiltonian Path Problem and the Node Cover Decision Problem for undirected graphs.} } @article{Martin-Vide:BEATCS:collapsing_hierarchy:2000, author={Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un}, title={Computing with Membranes. {O}ne More Collapsing Hierarchy}, journal={Bulletin of the EATCS}, year={2000}, month={October}, number={72}, pages={183--187} } @article{Calude:Complexity:Computing_with_:00, author={Cristian S. Calude and Gheorghe P{\u a}un}, title={Computing with Cells and Atoms in a Nutshell}, journal={Complexity}, year={2000}, volume={6}, number={1}, pages={38--48} } @article{Paun:J_COMPUT_SYST_SCI:Computing_with_:00, author={Gheorghe P{\u a}un}, title={Computing with Membranes}, journal={Journal of Computer and System Sciences}, year={2000}, volume={61}, number={1}, pages={108--143}, note={and Turku Center for Computer Science-TUCS Report No 208} } @article{Paun:IJFCS:Computing_with_:00, author={Gheorghe P{\u a}un}, title={Computing with Membranes ({P} systems): {A} variant}, journal={International Journal of Foundations of Computer Science}, year={2000}, month={March}, volume={11}, number={1}, pages={167--182}, note={and CDMTCS TR 098, Univ. of Auckland, 1999 (www.cs.auckland.ac.nz/CDMTCS).}, abstract={Membrane Computing is a recently introduced area of Molecular Computing, where a computation takes place in a membrane structure where multisets of objects evolve according to given rules (they can also pass through membranes). The obtained computing models were called P systems. In basic variants of P systems, the use of objects evolution rules is regulated by a given priority relation; moreover, each membrane has a label and one can send objects to precise membranes, identified by their labels. We propose here a variant where we get rid of both there rather artificial (non-biochemical) features. Instead, we add to membranes and to objects an 'electrical charge' and the objects are passed through membranes according to their charge. We prove that such systems are able to characterize the one-letter recursively enumerable languages (equivalently, the recursively enumerable sets of natural numbers), providing that an extra feature is considered: the membranes can be made thicker or thinner (also dissolved) and the communication through a membrane is possible only when its thickness is equal to 1. Several open problems are formulated.} } @article{Paun:FUND_INFORM:Membrane_Comput:00, author={Gheorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, title={Membrane Computing with External Output}, journal={Fundamenta Informaticae}, year={2000}, month={February}, volume={41}, number={3}, pages={313--340}, keywords={decidability, formal language, membrane computing, natural computing} } @article{Paun:J_UNIVERS_COMPUT_SCI:Simulating_H_Sy:00, author={Gheorghe P{\u a}un and Takashi Yokomori}, title={Simulating {H Systems} by {P} systems}, journal={Journal of Universal Computer Science}, year={2000}, volume={6}, number={1}, pages={178--193}, note={(www.iicm.edu/jucs). \url{http://www.jucs.org/jucs_6_1/simulating_h_systems_by}}, abstract={H systems are DNA computing models, based on the operation of splicing. P systems are membrane computing models, where objects can evolve in parallel in a hierarchical membrane structure. In particular, the objects can be strings and the evolution rules can be based on splicing. Both H systems with certain controls on the use of splicing rules and P systems of various types are known to be computationally universal, that is, they characterize the recursively enumerable languages. So, they are equivalent as the generative power. The present paper presents a direct simulation of some controlled H systems by splicing P systems. We achieve this goal for three basic regulation mechanisms: H systems with permitting contexts, H systems with forbidding contexts, and communicating distributed H systems. We can say that in this way we get a uniform 'implementation' of the three types of H systems in the form of a 'computing cell'.} } @article{Madhu_:ROMJIST:Inter-Membrane_:00, author={Mutyam Madhu and Kamala Krithivasan}, title={Inter-Membrane Communication in {P} systems}, journal={Romanian Journal of Information Science and Technology}, year={2000}, volume={3}, number={4}, pages={335--352}, abstract={In this paper, we propose a method for communication between any two non-adjacent membranes in a membrane system. In order to get this we propose a new variant of P systems, P systems with message carriers, in which, whenever a source membrane wants to send some message to a destination membrane, it will create a message carrier with that message and send it to the destination. Here we define various communication modes for inter-membrane communication. This new variant of a P system is able to solve Traveling Salesperson Problem for weighted complete graphs in a time linear in the number of nodes in the graph and can simulate CD grammar systems with an external control. By �external control� we mean controlling the sequence of components in action by a graph. We also prove that our new variant is computationally complete.} } @article{Krishna:IJCM:Sequential_parallel:2000, author = {Shankara Narayanan Krishna and Raghavan Rama}, title = {On the Power of {P} systems Based on Sequential/Parallel Rewriting}, journal = {International Journal of Computer Mathematics}, year = {2000}, volume = {77}, number = {1-2}, pages = {1--14}, } @article{Suzuki:ARTIF_LIFE:Chemical_Evolut:00, author={Yasuhiro Suzuki and Hiroshi Tanaka}, title={Chemical Evolution Among Artificial Proto-cells}, journal={Artificial Life}, year={2000}, volume={7}, pages={54--63} } @article{Suzuki:ROMJIST:On_a_LISP_Imple:00, author={Yasuhiro Suzuki and Hiroshi Tanaka}, title={On a {LISP} Implementation of a Class of {P} systems}, journal={Romanian Journal of Information Science and Technology}, year={2000}, volume={3}, number={2}, pages={173--186}, abstract={We consider a class of P systems, which we call Artificial Cell Systems (ACS), consisting of a membrane structure, multisets of symbols placed in its regions, and a set of rewriting rules acting in all the regions. Dissolving and creating membranes depends on the size of multisets. We have implemented such a system by using LISP, in the particular variant when the size of each multiset is bounded. Results of simulations of ACS evolution are reported.} } @article{Obtulo:IJFCS:Membrane_Comput:01, author={Adam Obtulowicz}, title={Membrane Computing and One-Way Functions}, journal={International Journal of Foundations of Computer Science}, year={2001}, month={August}, volume={12}, number={4}, abstract={There are presented certain membrane systems for computing the inverse of one-way functions in a polynomial time. The membrane systems are derived from some mathematical models of natural processes investigated in biochemistry and they have been introduced by Gh. Paun.} } @article{Obtulo:ROMJIST:Deterministic_P:01, author={Adam Obtulowicz}, title={Deterministic {P} systems for solving {SAT} Problem}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={195--202}, abstract={There are presented certain deterministic P-systems for solving SAT-problem in linear time. The P-systems and the processes generated by them have been introduced in the papers by Gheorghe Paun (P-Systems with Active Membranes: Attacking NP Complete Problems, Journal of Automata, Languages and Combinatorics, 6, pp. 75-90, 2000 and Computing with membranes, Journal of Computer and System Science, 61, 108-143, 2000).} } @article{Atanasiu:ROMJIST:Arithmetic_with:01, author={Adrian Atanasiu and Carlos Mart{\'i}n-Vide}, title={Arithmetic with Membranes}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={5--20}, abstract={P systems are computing models where certain objects can evolve in parallel into an hierarchical membrane structure. Recent results show that this model is a promising framework for solving NP-complete problems in polynomial time. The present paper considers the possibility to perform operations with integer numbers in a P system. All four arithmetical operations are implemented in a way which seems to have a lower complexity than when implementing them on usual computer chips.} } @article{Rodrig:BEATCS:On_the_Universa:01, author={Alfonso Rodriguez-Pat{\'o}n}, title={On the Universality of {P} systems with Membrane Creation}, journal={Bulletin of the EATCS}, year={2001}, month={June}, number={74}, pages={229--234} } @article{Paun:ROMJIST:On_P_Systems_wi:01, author={Andrei P{\u a}un}, title={On {P} systems with Partial Parallel Rewriting}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={203--210}, abstract={We settle here an open problem recently formulated by Krishna and Rama about P systems with partially parallel rewriting: we prove that such systems having only six membranes generate all the recursively enumerable languages.} } @article{Paun:Math.-Informatics_Series:Further_symport:2001, author={Andrei P{\u a}un and Gheorghe P{\u a}un and Alfonso Rodriguez-Pat{\'o}n}, title={Further remarks on {P} systems with symport rules}, journal={Ann. Univ. Al.I. Cuza Iasi, Math.-Informatics Series}, year={2001}, volume={10}, pages={3--18} } @article{Baranda:ROMJIST:Data_Structures:01, author={Angel V. Baranda and Juan Castellanos and Rafael Gonzalo and Fernando Arroyo and Luis-F. Mingo}, title={Data Structures for Implementing Transition {P} systems in Silico}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={21--32}, abstract={P systems are a new parallel and distributed computational model, based onn the membrane structure notion. In the regions defined by membranes, objects evolve according to given rules. In this way, we get transitions among system configurations, hence computations. Where and how P systems can be implemented is an open problem of the domain. One can look for implementations on a biochemical support (in vivo, or in vitro), on traditional computers. The implementation on digital computers can be a difficult task, at least because of the high degree of parallelism and non-determinism specific to P systems. However, this is an interesting challenge for computer researchers, and some attempts have already been done to simulate some variant of P Systems on a digital computer. This paper explores different data structures meant to facilitate the implementation of transition P systems on a digital computer. The presentation is structured in a such a manner to facilitate the understanding of the final representation of transition P systems into the proposed data structures. Firstly, we give a theoretical representation of P systems, including the necessary notation to understand their operational mode. Secondly, we study different data structures in which it is possible to represent P systems Finally, we propose a computational paradigm in order to determine the feasibility of simulating transition P systems by a program running on a digital computer.} } @article{Martin:BEATCS:Language_genera:01, author={Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un}, title={Language generating by means of membrane systems}, journal={Bulletin of the EATCS}, year={2001}, month={October}, number={75}, pages={199--218} } @article{Martin:CSJM:On_P_Systems_wi:01, author={Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un and Alfonso Rodriguez-Pat{\'o}n}, title={On {P} systems with Membrane Creation}, journal={Computer Science Journal of Moldova}, year={2001}, volume={9}, number={2}, pages={134--145} } @article{Martin:ROMJIST:P_Systems_with_:01, author={Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un and Alfonso Rodriguez-Pat{\'o}n}, title={{P} systems with Immediate Communication}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={171--182}, abstract={In the attempt to define P systems with the communication of objects through membranes controlled in an as simple as possible manner, we consider the case of string-objects (processed by rewriting or by splicing) with immediate communication: the string obtained by applying an evolution rule is immediately moved from the region where it is obtained to one of the neighboring regions, nondeterministically chosen. Rewriting P systems of this type (and without other controls on the communication or the rule application) are shown to generate only matrix languages, while for splicing P systems we obtain again the usual result from membrane system area: computational universality (that is, a characterization of recursively enumerable languages).} } @article{Zandron:ROMJIST:Using_Membrane_:01, author={Claudio Zandron and Claudio Ferretti and Giancarlo Mauri}, title={Using Membrane Features in {P} Systems}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={241--257}, abstract={In the basic variant of P systems, membranes are used as separators and as channels of communication. Other variants, introduced to obtain more 'realistic' models, consider membranes with different features: membranes of variable thickness, electrically charged membranes and active membranes (membranes can be divided to create new membranes). These features are not only useful to obtain 'realistic'models: we show how we can use them to get simpler and faster models. This work has been supported by the Italian Ministry of University (MURST), under project 'Unconventional Computational Models: Syntactic and Combinatorial Methods'.} } @article{Calude:JMVL:Glimpse:2001, author={Cristian S. Calude and Gheorghe P{\u a}un and Monica Tatar{\^a}m}, title={A Glimpse into Natural Computing}, journal={Journal of Multi-Valuate Logic}, year={2001}, volume={7}, pages={1--28} } @article{Paun:JALC:P_Systems_with_:01, author={Gheorghe P{\u a}un}, title={{P} systems with Active Membranes: Attacking {NP-Complete} Problems}, journal={Journal of Automata, Languages and Combinatorics}, year={2001}, volume={6}, number={1}, pages={75--90}, note={and CDMTCS TR 102, Univ. of Auckland, 1999 (www.cs. auckland.ac.nz/CDMTCS).} } @article{Paun:BioSystems:From_Cells_to_C:01, author={Gheorghe P{\u a}un}, title={From Cells to Computers: Computing with Membranes ({P} systems)}, journal={BioSystems}, year={2001}, month={March}, volume={59}, number={3}, pages={139--158}, abstract={The aim of this paper is to introduce to the reader the main ideas of computing with membranes, a recent branch of (theoretical) molecular computing. In short, in a cell-like system, multisets of objects evolve according to given rules in the compartments defined by a membrane structure and compute natural numbers as the result of halting sequences of transitions. The model is parallel, nondeterministic. Many variants have already been considered and many problems about them were investigated. We present here some of these variants, focusing on two central classes of results: (1) characterizations of the recursively enumerable sets of numbers and (2) possibilities to solve NP-complete problems in polynomial �� even linear �� time (of course, by making use of an exponential space). The results are given without proofs. An almost complete bibliography of the domain, at the middle of October 2000, is also provided.} } @article{Paun:INT_J_COMPUT_MATH:P_Systems_with_:01, author={Gheorghe P{\u a}un and Yasuhiro Suzuki and Hiroshi Tanaka}, title={{P} systems with Energy Accounting}, journal={International Journal of Computer Mathematics}, year={2001}, volume={78}, number={3}, pages={343--364} } @article{Georgescu:SUBBI:2001, author={H. Georgescu}, title={An efficient way to model P systems by X machine systems}, journal={Studia Univ. Babes-Bolyai, Informatica}, year={2001}, volume={46}, number={1}, pages={3--17} } @article{Liu:JXMI:Evolutionary_Dy:01, author={Jian Qin Liu and Katsunori Shimohara}, title={Evolutionary Dynamics for Heterogeneous {P} systems}, journal={Journal of Xi'an Mining Institute}, year={2001} } @article{Dassow:ActaCybernetica:P_Systems_with_:01, author={J{\"u}rgen Dassow and Gheorghe P{\u a}un}, title={{P} systems with Communication Based on Concentration}, journal={Acta Cybernetica}, year={2001}, volume={15}, number={1}, pages={9--24}, abstract={We consider a variant of P systems where the communication of objects is controlled by the 'concentration' of these objects: after each evolution step, the objects are redistributed among the regions of the system in such a way that each region contains the same number of copies of each object (plus/minus one, when the number of objects is not divisible by the number of regions). We show that P systems of this form, with only one flip-flop catalyst but without using other control ingredients, can generate the Parikh images of all matrix languages. When an unbounded number of catalysts is available, a characterization of recursively enumerable sets of vectors of natural numbers is obtained (by systems with only one membrane).} } @article{Dassow:ACTA_INFORM:Tree-Systems_of:01, author={J{\"u}rgen Dassow and Gheorghe P{\u a}un and Gabriel Thierrin and Sheng Yu}, title={Tree-Systems of Morphisms}, journal={Acta Informatica}, year={2001}, month={November}, volume={38}, number={2}, pages={131--153}, abstract={Starting from the idea of determinism in membrane systems, we introduce a language generating device consisting of morphisms placed in the nodes of a tree. Initial strings are given in the leaves; by iteratively applying the morphisms to them, we produce new strings, which are collected in the root of the tree. Such a device is called a tree-system of morphisms (in short, a T system). We investigate here the power of T systems, both in the extended (a terminal alphabet is considered and only strings over it are accepted) and non-extended case, mainly in comparison with classes of languages in Lindenmayer hierarchy.} } @article{Madhu_:ROMJIST:P_Systems_with_:01, author={Mutyam Madhu and Kamala Krithivasan}, title={{P} systems with Dynamic Membrane Polarization}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={135--154}, abstract={We propose here a variant of P systems with polarized membranes of variable thickness, in which the charge of a membrane is equal to the net charge of the string-objects it contains. As the charge of the membrane changes, applicable rules of that membrane will also change, i.e., the set of rules of a membrane with the positive charge is different from the set of rules of the same membrane with the negative charge or with the neutral charge. With this new variant of P systems, with degree 3 we achieve computational completeness. With a fixed membrane structure with each membrane having thickness one computational completeness is achieved with four membranes. A generalization of this system is also considered where computational completeness is achieved with two membranes.} } @article{Frisco:ROMJIST:On_Two_Variants:01, author={Pierluigi Frisco}, title={On Two Variants of Splicing {P} systems}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={89--100}, abstract={New computability models, called membrane systems or P systems, based on the evolution of objects in a membrane structure, were recently introduced. The seminal paper of Gheorghe Paun describes three ways to look at them: transition, rewriting and splicing P systems having different properties. Here we investigate two variants of splicing P systems improving results concerning their generative capability. One minimal result concerning the number of membranes used is obtained.} } @article{Freund:ROMJIST:Sequential_P_Sy:01, author={Rudolf Freund}, title={Sequential {P} systems}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={77--88}, abstract={We consider sequential variants of P-systems, the new model for computations using membrane structures and recently introduced by Gheorghe Paun. Using the permeabilty of the membranes for specific objects as a kind of filter turns out to be a very powerful mechanism in combination with suitable rules to be applied within the membranes. Generalized P-systems, GP-systems for short, constitute the most general model of sequential P-systems, considered in this paper. GP-systems allow for the simulation of graph-controlled grammars of arbitrary type based on productions working on single objects; for example, the general results we state in this paper can immediately be applied to the graph-controlled versions of context-free string grammars, n-dimensional -context-free array grammars, and elementary graph grammars. Moreover, we consider GP-systems as molecular computing devices using splicing or cutting and recombination of strings. Various variants of such systems have universal computational power, too, e.g., test tube systems based on splicing or cutting and recombination of strings can be simulated by the corresponding GP-systems.} } @article{Freund:BEATCS:Special_variant:01, author={Rudolf Freund}, title={Special variants of {P} systems inducing an infinite hiearchy with respect to the number of membranes}, journal={Bulletin of the EATCS}, year={2001}, month={October}, number={75}, pages={209--219} } @article{Krishna:ROMJIST:Hybrid_P_System:01, author={Shankara Narayanan Krishna and K. Lakshmanan and Raghavan Rama}, title={Hybrid {P} systems}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={111--123}, abstract={In this paper, we propose Hybrid P Systems, which are generative mechanisms using two types of rules: context-free rules and context adjoining rules. We prove that systems with seven membranes characterize the family of recursively enumerable languages. We also investigate the power of this variant with less than seven membranes by comparing it with the families of matrix languages, E0L and ET0L languages.} } @article{Krishna:AC:P_Sys_with_Pict_objs:2001, author={Shankara Narayanan Krishna and Kamala Krithivasan and Raghavan Rama}, title={{P} systems with Picture Objects}, journal={Acta Cybernetica}, year={2001}, volume={15}, number={1}, pages={53--74}, abstract={New computability models called P systems, based on the evolution of objects in a membrane structure, were recently introduced. In this paper, we consider two variants of P systems having ``complex objects'' like pictures as the underlying data structure. The first variant is capable of generating pictures with interesting patterns. We also investigate the generative power of this variant by comparing it with the families of two dimensional matrix languages. The second variant has some applications in pattern generation.} } @article{Krishna:JALC:P_Systems_with_:01, author={Shankara Narayanan Krishna and Raghavan Rama}, title={{P} systems with Replicated Rewriting}, journal={Journal of Automata, Languages and Combinatorics}, year={2001}, volume={6}, number={3}, pages={345--350} } @article{Krishna:BEATCS:A_Note_on_Paral:01, author={Shankara Narayanan Krishna and Raghavan Rama}, title={A Note on Parallel Rewriting in {P} systems}, journal={Bulletin of the EATCS}, year={2001}, month={February}, number={73}, pages={147--151} } @article{Head_To_Appear, author={Tom Head}, title={Aqueous Simulations of Membrane Computations}, journal={Romanian Journal of Information Science and Technology}, year={2001}, note={To appear}, abstract={A scheme of definitions that formalizes a limited family of membrane computations ispresented. The purpose is to provide a link between one of the approaches to biomolecular computation,called aqueous computing, and the newly developing concept of membrane computing, also called P-systems computing. This link allows one to view the already completed aqueous computations as wet labrealizations, or test tube simulations, of P-systems computations. It is hoped that the elementary linkageestablished here will be expanded and that it will suggest further developments in both P-systems and aqueous computing.} } @article{Manca:ROMJIST:Monoidals_for_M:01, author={Vincenzo Manca}, title={Monoidals for Molecules and Membranes}, journal={Romanian Journal of Information Science and Technology}, year={2001}, volume={4}, number={1-2}, pages={155--170}, abstract={Monoidals are computationally universal formalisms where a great quantity of other formalisms can be easily represented. Many symbolic systems from different areas are expressed as monoidals. The possibility is outlined that these systems express localization aspects typical of membrane systems and other phenomena such as temporality and multiplicity that are essential in the formalization of molecule manipulation systems.} } @article{Manca:JALC:On_the_Power_of:01, author={Vincenzo Manca and Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un}, title={On the Power of {P} systems with Replicated Rewriting}, journal={Journal of Automata, Languages and Combinatorics}, year={2001}, volume={6}, number={3}, pages={359--374} } @article{Atanas:FUND_INFORM:Recursive_Calcu:02, author={Adrian Atanasiu and Carlos Mart{\'i}n-Vide}, title={Recursive Calculus with Membranes}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={45--59}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={P systems are computing models where certain objects evolve in parallel in a hierarchical membrane structure. Recent results show that this model is a promising framework for solving NP-complete problems in polynomial time. A variant of P systems with active membranes is proposed in this paper. It uses a new operation called 'subordonation', based on the process of 'endocytosis' of membranes: a membrane can be entirely absorbed by another membrane, preserving its content. This class of P systems with active membranes can compute all Turing computable mappings. Arithmetical operations defined in [1] can be obtained as particular cases of primitive recursive functions, but with a higher complexity degree.} } @article{PerezJ:FUND_INFORM:Simulating_Turi:02, author={Alvaro Romero-Jim{\'e}nez and Mario J. P{\'e}rez-Jim{\'e}nez}, title={Simulating {T}uring Machines by {P} systems with External Output}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={273--278}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={In [3] a variant of the computation model introduced by Gh. P!un in [1] is considered: membrane systems with external output, which were proven to be universal, in the sense that they are able to generate all Parikh images of recursively enumerable languages. Here we give another proof of the universality of this model. The proof is carried out associating to each deterministic Turing machine a P system with external output that simulates its running. Thus, although we work with symbol-objects, we get strings as a result of computations, and in this way we generate directly all recursively enumerable languages, instead of their images through Parikh mapping, as it is done in [3].}, keywords={Natural computing, Membrane computing, Turing machines} } @article{Paun:NEW_GENERAT_COMPUT:The_Power_of_Co:02, author={Andrei P{\u a}un and Gheorghe P{\u a}un}, title={The Power of Communication: {P} systems with Symport/Antiport}, journal={New Generation Computing}, year={2002}, month={May}, volume={20}, number={3}, pages={295--305}, abstract={In the attempt to have a framework where the computation is done by communication only, we consider the biological phenomenon of trans-membrane transport of couples of chemicals (one say symport when two chemicals pass together through a membrane, in the same direction, and antiport when two chemicals pass simultaneously through a membrane, in opposite directions). Surprisingly enough, membrane systems without changing (evolving) the used objects and with the communication based on rules of this type are computationally complete, and this result is achieved even for pairs of communicated objects (as encountered in biology). Five membranes are used; the number of membranes is reduced to two if more than two chemicals may collaborate when passing through membranes.}, keywords={antiport, computational universality, membrane computing, molecular computing, symport} } @article{Paun:IJFCS:Comput_by_comm:2002, author={Andrei P{\u a}un and Gheorghe P{\u a}un and Grzegorz Rozenberg}, title={Computing by Communication in networks of Membranes}, journal={International Journal of Foundations of Computer Science}, year={2002}, month={December}, volume={13}, number={6}, pages={779--798}, abstract={In this paper we consider networks of membranes which compute by communication only, using symport/antiport rules. Such rules are used both for communication with the environment and for direct communication among membranes. It turns out that, rather surprisingly, networks with a small number of membranes are computationally universal. This is proved both for the case of three membranes where each membrane communicates with each other membrane, and for the case of four membranes consisting of two pairs such that only the membranes within each pair communicate directly. A single pair of communicating membranes can compute the Parikh images of matrix languages. Several open problems are also formulated.} } @article{Martin:J_UNIVERS_COMPUT_SCI:On_the_power_of:02, author={Carlos Mart{\'i}n-Vide and Andrei P{\u a}un and Gheorghe P{\u a}un}, title={On the power of {P} systems with symport rules}, journal={Journal of Universal Computer Science}, year={2002}, volume={8}, number={2}, pages={317--331}, abstract={A purely communicative variant of P systems was considered recently, based on the trans-membrane transport of couples of chemicals. When using both symport rules (the chemicals pass together in the same direction) and antiport rules (one chemical enters and the other exits a membrane), one obtains the computational completeness, and the question was formulated what happens when only symport rules are considered. We address here this question. First, we surprisingly find that 'generalized' symport rules are sufficient: if more than two chemicals pass together through membranes, then we get again the power of Turing machines. Three results of this type are obtained, with a trade-off between the number of chemicals which move together (at least three in the best case) and the number of membranes used. The same result is obtained for standard symport rules (couples of chemicals), if the passing through membranes is conditioned by some permitting contexts (certain chemicals should be present in the membrane). In this case, four membranes suffice. The study of other variants of P systems with symport rules (for instance, with forbidding contexts) is formulated as an open problem.} } @article{Martin:BEATCS:Membrane_Comput:02, author={Carlos Mart{\'i}n-Vide and Andrei P{\u a}un and Gheorghe P{\u a}un}, title={Membrane Computing: New Results, New Problems}, journal={Bulletin of the EATCS}, year={2002}, month={October}, number={78}, pages={204--212} } @article{Martin:FUND_INFORM:Membrane_system:02, author={Carlos Mart{\'i}n-Vide and Andrei P{\u a}un and Gheorghe P{\u a}un and Grzegorz Rozenberg}, title={Membrane systems with coupled transport: Universality and normal forms}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={1--15}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={This paper continues research on membrane systems which function by communication only, meaning that there are no evolving rules for molecules. The whole computation process relies on passage of molecules through membranes -- this provides communication between regions of the membrane system. Next to transport of single molecules through membranes (uniport) we also study a coupled transport of molecules, with two molecules passing either in the same direction (symport) or in opposite directions (antiport). We study the computational power of such membrane systems and prove that using only symport one gets Turing universality. Moreover, we prove that five membranes suffice to get Turing universality, and the number of membranes can be decreased to three if forbidding context conditions for transport are used.} } @article{Martin:THEOR_COMPUT_SCI:Membrane_System:02, author={Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un and Grzegorz Rozenberg}, title={Membrane Systems with Carriers}, journal={Theoretical Computer Science}, year={2002}, month={January}, volume={270}, number={1-2}, pages={779--796}, abstract={A membrane system is a model of computation which is inspired by some basic features of biological membranes. In this paper we consider another biologically inspired notion, viz., the notion of a carrier (or vehicle), as, e.g., used in gene cloning. We investigate the power of membrane systems where the rules for the evolving of objects are replaced by the rules that carry objects (by vehicles) through membranes. It turns out that these systems (even with a small number of membranes, a small number of carriers, and a small number of passengers taken by carriers) are computationally universal.}, keywords={P systems, Turing computability, membrane computing, molecular computing, natural computing} } @article{Martin:CyS:On_the_Power_of:02, author={Carlos Mart{\'i}n-Vide and Victor Mitrana and Gheorghe P{\u a}un}, title={On the Power of {P} systems with Valuations}, journal={Computaci{\'o}n y Sistemas}, year={2002}, volume={5}, number={2}, pages={120--127} } @article{NicolauJr:FUND_INFORM:C_Library:02, author={Dan V. {Nicolau Jr.} and Gerardin Solana and Florin Fulga and Dan V. Nicolau}, title={A {C} Library for Simulating {P} Systems}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={241--248}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={The present paper describes an ANSI C library which has been developed to facilitate the implementation and simulation of P systems on a computer. Simple data structures are proposed which permit the representation of membranes and their associated objects, and facilities are provided for implementing both 'active' and 'non-active' membrane systems, including actions for dissolving a membrane, dividing an existing membrane and creating a new membrane.}, keywords={P systems, Software, Membranes, Simulation} } @article{Arroyo:J_UNIVERS_COMPUT_SCI:Membrane_Comput:02, author={Fernando Arroyo and Angel Baranda and Juan Castellanos and Gheorghe P{\u a}un}, title={Membrane Computing: The Power of (Rule) Creation}, journal={Journal of Universal Computer Science}, year={2002}, volume={8}, number={3}, pages={369--381}, abstract={We consider a uniform way of treating objects and rules in P systems: we start with multisets of rules, which are consumed when they are applied, but the application of a rule may also produce rules, to be applied at subsequent steps. We find that this natural and simple feature is surprisingly powerful: systems with only one membrane can characterize the recursively enumerable languages, both in the case of rewriting and of splicing rules; the same result is obtained in the case of symbol?objects, for the recursively enumerable sets of vectors of natural numbers.} } @article{Ciobanu:FUND_INFORM:Gene_Expression:02, author={Gabriel Ciobanu and Bogdan Tanasa}, title={Gene Expression by Software Mechanisms}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={67--80}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={This paper describes the molecular interactions and coordination of cell processes using computer operating system concepts related to synchronization and communication. We argue that in molecular biology, the genes and their chromatin context provide communication and interaction with various cell processes in a similar way to that in which computer processes synchronize and communicate with each other.}, keywords={Cell biology, operating systems, process communication, pipe, signals, modules} } @article{Ciobanu:FUND_INFORM:Membrane_Softwa:02, author={Gabriel Ciobanu and Dorin Paraschiv}, title={{P} System Software Simulator}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={61--66}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={We present a software application that is intended to be a tool for people working with P~systems. This software tool is called the Membrane Simulator and it provides a graphical simulation for two variants of P systems: the initial version of the catalytic hierarchical cell system and the active membrane system.} } @article{Paun:THEOR_COMPUT_SCI:A_Guide_to_Memb:02, author={Gheorghe P{\u a}un and Grzegorz Rozenberg}, title={A Guide to Membrane Computing}, journal={Theoretical Computer Science}, year={2002}, month={September}, volume={287}, number={1}, pages={73--100}, abstract={Membrane systems are models of computation which are inspired by some basic features of biological membranes. In a membrane system multisets of objects are placed in the compartments defined by the membrane structure, and the objects evolve by means of 'reaction rules' also associated with the compartments, and applied in a maximally parallel, nondeterministic manner. The objects can pass through membranes, the membranes can change their permeability, they can dissolve, and they can divide. These features are used in defining transitions between configurations of the system, and sequences of transitions are used to define computations. In the case of symbol-objects, we compute a set of numbers, and in the case of string-objects we compute a set of strings, hence a language. Many different classes of such computing devices (now called P systems) have already been investigated. Most of them are computationally universal, i.e., equal in power to Turing machines. Systems with an enhanced parallelism are able to trade space for time and solve in this way (at least in principle), by making use of an exponential space, intractable problems in a feasible time. The present paper presents the basic ideas of computing with membranes and some fundamental properties (mostly concerning the computational power and efficiency) of P systems of various types.}, keywords={Chomsky hierarchy, NP-complete problems, membrane computing, natural computing, turing computability} } @article{Ardele:FUND_INFORM:The_relevance_o:02, author={Ioan I. Ardelean}, title={The Relevance of Cell Membranes for {P} systems. {G}eneral Aspects}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={35--43}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={This paper presents the stucture, organization (hierarchy) and function of cell membrane in bacteria, with special emphasis on: i) the hierarchy of cell membranes in Gram-negative and Gram-positive bacteria, ii) two main criteria for the classification of transport of ions and molecules across cell membrane, iii) two important mechanisms of transport - symport and antiport, and iv) the relevance of these biological realities for working concepts in P systems such as membrane hierarchy and developmental rules. The biological reality not only illustrates some central concepts in P systems but also could give some suggestions for the theoretical development of P systems and their possible implementation.} } @article{Giavitto:FUND_INFORM:The_topological:02, author={Jean Louis Giavitto and Olivier Michel}, title={The Topological Structures of Membrane Computing}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={123--145}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={In its initial presentation, the P system formalism describes the topology of the membranes as a set of nested regions. In this paper, we present an algebraic structure developped in combinatorial topology that can be used to describe finer adjacency relationships between membranes. Using an appropriate abstract setting, this technical device enables us to reformulate also the computation within a membrane and proposes a unified view on several computational mechanisms initially inspired by biological processes. These theoretical tools are instantiated in MGS, an experimental programming language handling various types of membrane structures in a homogeneous and uniform syntax.}, keywords={membrane computing, Gamma, CHAM, P system, L system, cellular automata, group based fields, rewriting, topological collection, declarative programming language} } @article{Aguado:FUND_INFORM:P_Systems_with_:02, author = {Joaquin Aguado and Tudor Balanescu and Tony Cowling and Marian Gheorghe and Mike Holcombe and Florentin Ipate}, title = {{P} systems with Replicated Rewriting and Stream {X-Machines} ({Eilenberg}, machines)}, journal = {Fundamenta Informaticae}, year = {2002}, month = {January}, volume = {49}, number = {1-3}, pages = {17--33}, note = {Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract = {The aim of this paper is to show how the P systems with replicated rewriting can be modeled by X-machines (also called Eilenberg machines). In the first approach, the parallel behaviour of the regions of a P system is simulated by a sequential process involving a single X-machine. This allows the application of the X-machine testing procedures in order to prove the correctness of P systems. In the second approach, a P system is simulated by a communicating system of X-machines. Each component of such a system is an X-machine associated with a region of the given P system. The components act in parallel, as their counterparts do in a P system, and use some specific mechanism for communication and synchronisation.}, keywords = {P Systems, Finite state machines, (Stream) X-machines, Formal specifications}, } @article{Mate:FUND_INFORM:On_the_power_of:02, author={Jos{\'e} L. Mat{\'e} and Alfonso Rodr{\'i}guez-Pat{\'o}n and Andr{\'e}s Silva}, title={On the power of {P} systems with {DNA-worm-objects}}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={229--239}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={We introduce a variant of P systems with string-objects - called worm-objects - inspired in the DNA computing area. These systems work with multisets of string-objects processed by splitting, mutation, replication and recombination. This model is simpler (we eliminate the replication operation) and more realistic (the recombination operation is changed by the simpler one of suffix-prefix or head-tail concatenation developed in the DNA computing framework) than the previous one. The result of a computation is the set of strings sent out of the system. We work with multisets of strings but we generate languages instead of sets of numbers. We prove that, without priority among rules or other control mechanisms, (1) these P systems with at most three membranes can generate all recursively enumerable languages, (2) with non-decreasing length mutation and splitting rules, three membranes are enough to generate the family of context-sensitive languages, and (3) with these restricted types of splitting and mutation rules, four membranes can generate the family of recursively enumerable languages.}, keywords={Membrane computing, P systems, Recursively enumerable languages} } @article{Madhu_:FUND_INFORM:Contextual_P_Sy:02, author={Kamala Krithivasan and Mutyam Madhu}, title={Contextual {P} systems}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={179--189}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={Generally, in P systems with string-objects one uses the Chomsky way of rewriting for processing the objects. In this paper we consider the contextual way of handling string-objects in P systems. We introduce some variants of contextual grammars and prove that contextual P systems with rules corresponding to these variants are more powerful than ordinary contextual grammars and their variants. We also show that one-sided contextual P systems with right-sided erased contexts and insertion contextual P systems with right-sided erased contexts are computationally complete.}, keywords={P systems, contextual grammars, insertion grammars, contextual P systems, recursively enumerable languages, Kuroda normal form, Pentonnen normal form, computational completeness} } @article{Kudlek:FUND_INFORM:Closure_Propert:02, author={Manfred Kudlek and Victor Mitrana}, title={Closure Properties of Multiset Language Families}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={191--203}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={Multiset languages are languages defined by multiset grammars in the sense of [4]. We extend to multiset languages the usual operations defined for string languages and define new operations specific for multiset languages. The closure properties of the main classes of multiset languages are investigated. Along these lines we introduce two notions of abstract family of multiset languages.}, keywords={Multisets, Closure Properties} } @article{PerezJ:ROMJIST:Verifying_a_P:02, author={Mario J. P{\'e}rez-Jim{\'e}nez and Fernando Sancho-Caparrini}, title={Verifying a {P} system generating squares}, journal={Romanian Journal of Information Science and Technology}, year={2002}, volume={5}, number={2-3} } @article{PerezJ:FUND_INFORM:A_formalization:02, author={Mario J. P{\'e}rez-Jim{\'e}nez and Fernando Sancho-Caparrini}, title={A Formalization of Transition {P} systems}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={261--271}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={In this paper we give a complete formalization of a new computability model of a distributed parallel type which is inspired by some basic features of living cells: transition P systems as they were given in [3], addressed with completely different techniques than in [1] and [2]. For this, we present a formal syntax and semantic of the transition P systems capturing the synchronized work of P systems, and the nondeterministic and maximally parallel manner in which the rules of these systems can be applied.}, keywords={Natural computing, P system, Formal verification} } @article{Madhu:Grammars:A_Note_on_Hybri:02, author={Mutyam Madhu and Kamala Krithivasan}, title={A Note on Hybrid {P} systems}, journal={Grammars}, year={2002}, month={December}, volume={5}, number={3}, pages={239--244}, abstract={Generally, in rewriting P systems (Martin-Vide and Paun, 2000) one uses Chomsky rules (Hopcroft and Ullman, 1979), whereas in contextual P systems (Madhu and Krithivasan, 2002) we considered contextual rules (Marcus, 1969), (Paun, 1997) for processing string-objects. By combining Chomsky rules and contextual rules, a new class of P systems were introduced in Krishna et al. (2001), the hybrid P systems. In this paper we continue the study of hybrid P systems, and show that systems with two membranes are universal in the case of contextual rules with a regular choice, and systems with four membranes are universal in the case of contextual rules with finite selection.} } @article{Madhu_:ACTA_INFORM:Generalized_Nor:02, author={Mutyam Madhu and Kamala Krithivasan}, title={Generalized Normal Forms for Rewriting {P} systems}, journal={Acta Informatica}, year={2002}, month={September}, volume={38}, number={10}, pages={721--734}, abstract={P systems, introduced by Gh. Paun [9] as a new theoretical model for molecular computations, are based on the notion of membrane structure. Several variants of P systems have been proposed and shown to be computationally universal. One of such variant is the rewriting P systems, where we consider string-objects and process them using rewriting rules. Particular cases of normal forms for rewriting P systems were proposed in [11-13]. In this work we introduce the generalized normal form for rewriting P systems which take into consideration the depth of the membrane structure and the number of rewriting rules present in each membrane. Such generalized normal forms are given for rewriting P systems with priorities, and for partially parallel rewriting P systems. In this way, several results from the literature are generalized and improved.} } @article{Madhu_:BEATCS:Improved_Result:02, author={Mutyam Madhu and Kamala Krithivasan}, title={Improved Results about Universality of {P} systems}, journal={Bulletin of the EATCS}, year={2002}, month={February}, number={76}, pages={162--168} } @article{Bottoni:ACTA_INFORM:Promoters_Inhibitors:2002, author={Paolo Bottoni and Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un and Grzegorz Rozenberg}, title={Membrane systems with promoters/inhibitors}, journal={Acta Informatica}, year={2002}, month={September}, volume={38}, number={10}, pages={695--720}, abstract={Abstract. The computational model of membrane computing (formalized through membrane systems, also called P systems) is based on the way that biological membranes define compartments, each having its set of molecules and (enzymes enhancing) reactions, with compartments communicating through the transport of molecules through membranes. In this paper we augment the basic model of membrane systems with promoters and inhibitors, which formalize the reaction enhancing and reaction prohibiting roles of various substances (molecules) present in cells. We formalize such membrane systems with promoters/inhibitors and investigate their basic properties. In particular we establish universality results, i.e., we provide characterizations of recursively enumerable sets (of vectors of natural numbers) using these systems. It turns out that systems with promoters/inhibitors achieve universal computations without using the standard 'auxiliary' features of membrane systems, for instance, without using catalysts.} } @article{Frisco:FUND_INFORM:A_Direct_Constr:02, author={Pierluigi Frisco and Hendrik Jan Hoogeboom and Paul Sant}, title={A Direct Construction of a Universal {P} system}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={103--122}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={We present a direct universal P system based on splicing. Our approach differs from those shown in previous papers as the P system we construct takes as input an encoding of another P system. Previous results were based on the simulation of universal type-0 grammars or Turing machines. We think that the approach we use can be applied to other variants of P systems.}, keywords={DNA computing, P systems, Splicing, Direct universal system} } @article{Freund:BEATCS:A_Short_Note_on:02, author={Rudolf Freund and Marion Oswald}, title={A Short Note on Analysing {P} systems with Antiport Rules}, journal={Bulletin of the EATCS}, year={2002}, month={October}, number={78}, pages={231--236} } @article{Freund:FUND_INFORM:GP_systems_with:02, author={Rudolf Freund and Marion Oswald}, title={{GP Systems} with forbidding context}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={81--102}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={We consider extended variants of GP systems, i.e., membrane systems with sequential applications of evolution rules. The main features we explore are applicability conditions (context conditions) on single objects as well as on the remaining contents of the underlying compartment. For a special very restricted variant only using forbidding context conditions we already obtain universal computational power.} } @article{Marcus:FUND_INFORM:Membranes_versu:02, author={Salomon Marcus}, title={Membranes versus {DNA}}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={223--227}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={Based on some recent arguments brought into attention by some important authors, we point out the insufficiency of DNA in explaining life and the importance of membranes in bridging this gap. We also discuss the delicate, still open problem concerning the mathematical status of membrane.} } @article{Krishna:FUND_INFORM:On_the_Power_of:02, author={Shankara Narayanan Krishna and K. Lakshmanan and Raghavan Rama}, title={On the Power of {P} systems with Contextual Rules}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={167--178}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={We consider P Systems with string objects which evolve by means of one-sided contextual rules and erasing contextual rules. The generative power of these systems with three or less than three membranes is investigated. We show that systems with three membranes characterize the family of recursively enumerable languages. When the string replication is used in one-sided contextual rules, these systems are able of solving NP-complete problems in linear time: this is exemplified with SAT and HPP.}, keywords={P Systems, One-sided contextual rules, Erasing contextual rules, Recursively enumerable, NP-completeness} } @article{Ji:FUND_INFORM:The_Bhopalator::02, author={Sungchul Ji}, title={The {Bhopalator}: An Information/Energy Dual Model of the Living Cell}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={147--165}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={A molecular model of the living cell known as the Bhopalator is described with the hope of aiding mathematicians and computer scientists to develop comprehensive algebraic models of the cell. The Bhopalator is energy/information dual in the sense that it can be described using two complementary languages - the energy/matter based language of physics and chemistry and the information/sign based language of linguistics and mathematics. The availability of mathematical models of the cell may eventually lead to developing computer models of the living cell, resulting in important applications not only in biology and medicine but also in computer science and computer industry. To stimulate discussions among mathematicians and computer scientists, the algebraic encoding of the essential characteristics of the Bhopalator may be referred to as the C system (C indicating the cell), in analogy to the well-known H and P systems.} } @article{Nishida:FUND_INFORM:Simulations_of_:02, author={Taishin Yasunobu Nishida}, title={Simulations of Photosynthesis by a {K-Subset} Transforming System with Membranes}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={249--259}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={By considering the inner regions of living cells' membranes, P systems with inner regions are introduced. Then, a new type of membrane computing systems are considered, called $K$-subset transforming systems with membranes, which can treat nonintegral multiplicities of objects. As an application, a K-subset transforming system is proposed in order to model the light reactions of the photosynthesis. The behaviour of such systems is simulated on a computer.}, keywords={P System, nonintegral multiplicity, K-subset, photosynthesis} } @article{Manca:FUND_INFORM:DNA_and_membran:02, author={Vincenzo Manca}, title={{DNA} and membrane algorithms for {SAT}}, journal={Fundamenta Informaticae}, year={2002}, month={January}, volume={49}, number={1-3}, pages={205--221}, note={Special Issue: Membrane Computing (WMC-CdeA2001) Guest Editor(s): Carlos Mart{\'i}n-Vide, Gheorghe P{\u a}un}, abstract={Some DNA algorithms proposed in the literature for propositional satisfiability (SAT) are analyzed. In the class of 'extract model' the two sub-classes of 'literal string' and 'clause string' algorithms are compared and a new formulation of these algorithms is given in terms of membrane systems. Then, the duality between literal string and clause string formulation of SAT is expressed by means of 'singleton matrices' that introduce another membrane algorithm for SAT. The analysis developed suggests the perspective of membrane systems as problem-solving agents based on molecule localization, transformation, and propagation.}, keywords={Satisfiability, DNA Computing, Membrane Systems, Molecular Computing, Unconventional Computing Models} } @article{Obtulowicz:NC:Math_Models_Uncertainty:2003, author={Adam Obtulowicz}, title={Mathematical Models of Uncertainty with a Regard to Membrane Systems}, journal={Natural Computing}, year={2003}, month={August}, volume={2}, number={3}, pages={251--263}, abstract={A brief review is presented of the known mathematical models of uncertainty taking into account its grounds such as randomness, indiscernibility, and vagueness. Then, one discusses the models of the uncertainty caused by indiscernibility and random indiscernibility with a regard to membrane systems. The discussed models include rough sets, probabilistic rough sets, and probabilistic fuzzy sets. An algebraic characterization of P systems is presented, which makes possible to 'transfer' the methods of Petri net theory to P system theory including the approach of the first theory to models of uncertainty.}, keywords={Petri nets, fuzzy sets, membrane computing, probability, rough sets} } @article{Obtulo:BioSystems:(In_search_of)_:03, author={Adam Obtulowicz and Gheorghe P{\u a}un}, title={({I}n search of) {P}robabilistic {P} systems}, journal={BioSystems}, year={2003}, month={July}, volume={70}, number={2}, pages={107--121}, abstract={The aim of this paper is to (preliminarily) discuss various ways of introducing probabilities in membrane systems. We briefly present both ideas already circulated in the literature and new proposals, trying to have a systematic overview of possibilities of associating probabilities with the ingredients of a membrane system: with (localization of) single objects, with multiplicities of objects (hence with the multisets), with the rules (depending or not on the previous applied rule), with the communication targets. For a certain mode of using the probabilities associated with the evolution rules (in string-object P systems) we obtain the computational universality.} } @article{Alhazov.etal:PSPACE:FI2003, author = {Artiom Alhazov and Carlos Mart{\'i}n-Vide and Linqiang Pan}, title = {Solving a {PSPACE}-Complete Problem by Recognizing {P} Systems with Restricted Active Membranes}, journal = {Fundamenta Informaticae}, year = {2003}, volume = {58}, number = {2}, pages = {67--77}, abstract = {P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. Recently, Petr Sos{\'i}k has shown that a semi-uniform family of P systems with active membranes and 2-division is able to solve the PSPACE-complete problem QBF-SAT in linear time; he has also conjectured that the membrane dissolving rules of the (d) type may be omitted but probably not the (f) type rules for non-elementary membrane division. In this paper, we partially confirm the conjecture proving that dissolving rules are not necessary. Moreover, the construction is now uniform. It still remains open whether or not non-elementary membrane division is needed.}, keywords = {Membrane computing, P system, PSPACE-complete problem, QBF-SAT problem}, url = {http://iospress.metapress.com/content/99n72anvn6bkl4mm/}, } @article{Martin:TCS:Tissue_P_Systems:2003, author={Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un and Juan Pazos and Alfonso Rodr{\'i}guez-Pat{\'o}n}, title={Tissue {P} systems}, journal={Theoretical Computer Science}, year={2003}, month={March}, volume={296}, number={2}, pages={295--326}, abstract={Starting from the way the inter-cellular communication takes place by means of protein channels (and also from the standard knowledge about neuron functioning), we propose a computing model called a tissue P system, which processes symbols in a multiset rewriting sense, in a net of cells. Each cell has a finite state memory, processes multisets of symbol-impulses, and can send impulses ('excitations') to the neighboring cells. Such cell nets are shown to be rather powerful: they can simulate a Turing machine even when using a small number of cells, each of them having a small number of states. Moreover, in the case when each cell works in the maximal manner and it can excite all the cells to which it can send impulses, then one can easily solve the Hamiltonian Path Problem in linear time. A new characterization of the Parikh images of ETOL languages is also obtained in this framework. Besides such basic results, the paper provides a series of suggestions for further research.}, keywords={Chomsky hierarchy, Lindenmayer hierarchy, NP-complete problems, P systems, membrane computing, natural computing} } @article{Ferretti:TCS:On_Tree_Variants_of_rew_P_Sys:2003, author={Claudio Ferretti and Giancarlo Mauri and Gheorghe P{\u a}un and Claudio Zandron}, title={On three variants of rewriting {P} systems}, journal={Theoretical Computer Science}, year={2003}, month={May}, volume={301}, number={1-3}, pages={201--215}, abstract={We continue here the study of P systems with string objects processed by rewriting rules, by investigating some questions which are classic in formal language theory: leftmost derivation, conditional use of rules (permitting and forbidding conditions), relationships with language families in Chomsky and Lindenmayer hierarchies.}, keywords={Chomsky hierarchy, Lindenmayer systems, membrane computing, regulated rewriting} } @article{Besozzi:BioSystems:P_systems_with_:03, author = {Daniela Besozzi and Claudio Ferretti and Giancarlo Mauri and Claudio Zandron}, title = {{P} Systems with deadlock}, journal = {BioSystems}, year = {2003}, month = {July}, volume = {70}, number = {2}, pages = {95--105}, abstract = {Rewriting P systems with parallel application of evolution rules, as defined in Besozzi et al. [Parallel rewriting P systems with deadlock. In: M. Hagiya and A. Ohuchi (Eds.), Pre-Proceedings of DNA8 Conference, Hokkaido University Japan, June 2002a, pp. 171--183], are considered here. Different kinds of parallelism methods are defined for string rewriting. The notion of deadlock is then introduced to describe situations where rules with mixed target indications are simultaneously applied to a common string. The generative power of parallel P systems with deadlock is analyzed, with respect to Lindenmayer systems, and some relations among different types of parallel P systems with or without deadlock, allowing to rewrite all occurrences of a single symbol, or all the symbols applying either any of the rules or only those belonging to a specific set (table) of rules are studied. Some open problems are also formulated.}, } @article{Besozzi:TCS:Gemmating_P_Systems:2003, author={Daniela Besozzi and Giancarlo Mauri and Gheorghe P{\u a}un and Claudio Zandron}, title={Gemmating {P} systems: collapsing hierarchies}, journal={Theoretical Computer Science}, year={2003}, month={March}, volume={296}, number={2}, pages={253--267}, abstract={We continue the analysis of P systems with gemmation of mobile membranes. We solve an open problem from Besozzi et al. (Proc. Italian Conf. on Theoretical Computer Science 2001, Lecture Notes in Computer Science, Vol. 2202, Springer, Berlin, 2001, pp. 136-153), showing that the hierarchy on the number of membranes collapses: systems with eight membranes characterize the recursively enumerable languages (seven membranes are enough in the case of extended systems). We also prove that P systems, which use only gemmation, but neither classical rewriting rules nor in/out communications, can generate the same family of languages. In this case, the hierarchy on the number of membranes collapses to level nine.}, keywords={matrix grammar, membrane computing, recursively enumerable languages, universality} } @article{Csuhaj:NC:From_Watson_Crick_L_Systems_to:2003, author={Erzs{\'e}bet Csuhaj-Varj{\'u} and Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un and Arto Salomaa}, title={From {W}atson-{C}rick {L} {Systems} to {Darwinian} {P} systems}, journal={Natural Computing}, year={2003}, month={August}, volume={2}, number={3}, pages={299--318}, abstract={Watson-Crick L systems are language generating devices making use of Watson-Crick complementarity, a fundamental concept of DNA computing. These devices are Lindenmayer systems enriched with a trigger for complementarity transition: if a 'bad' string is obtained, then the derivation continues with its complement which is always a 'good' string. Membrane systems or P systems are distributed parallel computing models which were abstracted from the structure and the way of functioning of living cells. In this paper, we first interpret the results known about the computational completeness of Watson-Crick E0L systems in terms of membrane systems, then we introduce a related way of controlling the evolution in P systems, by using the triggers not in the operational manner (i.e., turning to the complement in a 'bad' configuration), but in a 'Darwinian' sense: if a 'bad' configuration is reached, then the system 'dies', that is, no result is obtained. The triggers (actually, the checkers) are given as finite state multiset automata. We investigate the computational power of these P systems. Their computational completeness is proved, even for systems with non-cooperative rules, working in the non-synchronized way, and controlled by only two finite state checkers; if the systems work in the synchronized mode, then one checker for each system suffices to obtain the computational completeness.}, keywords={L system, P system, Watson-Crick complementarity, membrane computing, recursively enumerable language} } @article{Bernardini:NC:PXSystems:2003, author={Francesco Bernardini and Marian Gheorghe and Mike Holcombe}, title={{PX systems} = {P} systems + {X} machines}, journal={Natural Computing}, year={2003}, month={August}, volume={2}, number={3}, pages={201--213}, abstract={The paper is a survey of the main features of P systems, X machines and of a new computational device called PX system. The sequential and the parallel PX systems are presented. Results reflecting the computational power of these models and their effectiveness in solving NP-complete problems are briefly mentioned.}, keywords={P systems, Turing computability, X machines, molecular computing} } @article{Bernardini:BioSystems:Dynamical_aspec:03, author={Francesco Bernardini and Vincenzo Manca}, title={Dynamical aspects of {P} systems}, journal={BioSystems}, year={2003}, month={July}, volume={70}, number={2}, pages={85--93}, abstract={A dynamical analysis of P systems is given that is focused on basic phenomena of biological relevance. After a short presentation of a new kind of P systems (PB systems), membrane systems with environment, called PBE systems, are introduced that are more suitable for modeling complex membrane interactions. Some types of periodicity and non-periodicity are considered for PBE systems by showing some 'minimal' examples of systems that exhibit these properties. In particular, a discrete formulation of the Belousov�Zhabotinsky (BZ) reaction is given in terms of PBE systems. Some questions and open problems for future research are indicated.} } @article{Ciobanu:BioSys:Distributed_algorithms:2003, author={Gabriel Ciobanu}, title={Distributed algorithms over communicating membrane systems}, journal={BioSystems}, year={2003}, month={July}, volume={70}, number={2}, pages={123--133}, abstract={This paper presents fundamental distributed algorithms over membrane systems with antiport carriers. We describe distributed algorithms for collecting and dispersing information, leader election in these systems, and the mutual exclusion problem. Finally, we consider membrane systems producing correct results despite some failures at some of the components or the communication links. We show that membrane systems with antiport carriers provide an appropriate model for distributed computing, particularly for message-passing algorithms interpreted here as membrane transport in both directions, namely when two chemicals behave as input and output messages and pass the membranes in both directions using antiport carriers.}, keywords={Membrane systems; Antiport carriers; Distributed and parallel computing; Broadcast; Convergecast; Flooding; Leader election; Mutual exclusion; Fault tolerance; Consensus} } @article{Paun:Theoria:Recent_computing_models:2003, author={Gheorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez}, title={Recent computing models inspired from Biology: {DNA} and membrane computing}, journal={Theoria}, year={2003}, volume={18}, number={46}, pages={71--84}, abstract={We briefly present two areas of natural computing, vividly investigated in the recent years: DNA computing and membrane computing. Both of them have the roots in cellular biology and are rather developed at the theoretical level (new concepts, models, paradigms of computer science, with mathematical and epistemological significance have been considered in this framework), but both areas are still looking for implementations of a practical interest.}, keywords={Computer Science, Mathematics, Turing computability, Biochemistry, DNA computing, Membrane Computing.} } @article{Ardelean:NC:Modelling_Bio_Process:2003, author={Ioan I. Ardelean and Matteo Cavaliere}, title={Modelling biological processes by using a probabilistic {P} system software}, journal={Natural Computing}, year={2003}, month={July}, volume={2}, number={2}, pages={173--197}, abstract={In this paper we present a probabilistic P system simulator that implements the evolution-communication model proposed in (Cavaliere, 2003) enriched with some probabilistic parameters inspired by the cell biology. After describing the software and its working, we compare the mathematical model used with the biological reality of the cell. Then, we present some mathematical and biological applications showing how one can use this software to simulate simple but interesting biological phenomena, related to respiration and photosynthesis processes in some bacteria.}, keywords={bacteria, membrane computing, photosynthesis, probability, respiration, software} } @article{Krithivasan:BEATCS:minimising_finite_state:2003, author={Kamala Krithivasan and Sandeep V. Varma}, title={On minimising finite state {P} automata}, journal={Bulletin of the EATCS}, year={2003}, month={July}, volume={80}, pages={168--173} } @article{PerezJ:NC:Complexity_Classes:2003, author={Mario J. P{\'e}rez-Jim{\'e}nez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, title={Complexity classes in models of cellular computing with membranes}, journal={Natural Computing}, year={2003}, month={August}, volume={2}, number={3}, pages={265--285}, abstract={In this paper we introduce four complexity classes for cellular computing systems with membranes: the first and the second ones contain all decision problems solvable in polynomial time by a family of deterministic P systems, without and with an input membrane, respectively; the third and fourth classes contain all decision problems solvable in polynomial time by a family of non-deterministic P systems, without and with an input membrane, respectively. We illustrate the usefulness of these classes by solving two NP�complete problems, namely HPP and SAT, in both variants of P systems.}, keywords={P systems, complexity classes, membrane computing} } @article{Cavaliere:NC:Forbidding_and_enforcing:2003, author={Matteo Cavaliere and Nata{\u s}a Jonoska}, title={Forbidding and enforcing in membrane computing}, journal={Natural Computing}, year={2003}, month={August}, volume={2}, number={3}, pages={215--228}, abstract={Motivated by biochemistry and the non-deterministic reactions between molecules, the authors in (Ehrenfeucht and Rozenberg, 2003) introduced the concept of forbidding-enforcing systems (fe-systems) that define families of languages. Using the same concept we propose to study forbidding and enforcing within membrane systems. Two approaches are presented; in the first case the membrane system generates families of languages and in the second case the membrane system generates a single language. We show that by using forbidding-enforcing in membranes, families of languages that cannot be defined by any fe-system can be generated. When a single language is generated, we show that SAT can be solved in a constant time (at price of using an exponential space). Also we show an example of a context-free language that can be generated without any forbidders.}, keywords={DNA computing, forbidding-enforcing, languages, membrane computing} } @article{Ionescu:NaturalComputing:Unexpected:03, author={Mihai Ionescu and Carlos Mart{\'i}n-Vide and Andrei P{\u a}un and Gheorghe P{\u a}un}, title={Unexpected universality results for three classes of {P} systems with symport/antiport}, journal={Natural Computing}, year={2003}, month={December}, volume={2}, number={4}, pages={337--348}, abstract={Symport and antiport are biological ways of transporting molecules through membranes in ``collaborating'' pairs; in the case of symport the two molecules pass in the same direction, in the case of antiport the two molecules pass in opposite directions. Here we first survey the results about the computing power of membrane systems (P systems) using only symport/antiport rules (hence these systems compute by communication only), then we consider a recently introduced, way of defining the result of a computation in a membrane system: looking for the trace of certain objects in their movement through membranes. Rather unexpected, in this way we get characterizations of recursively enumerable languages by means of membrane systems with symport/antiport which work with multisets of objects (note the qualitative difference between the data structure used by computations � multisets: no ordering � and the data structure of the output � strings: linear ordering). A similar remark holds true for the case of analysing P systems, which work in an automata-like manner: the sequence of certain distinguished objects taken from the environment during a computation is the string recognized by the computation. We also survey universality results from this area, with sketched proofs. Some open problems are also formulated.}, keywords={Chomsky hierarchy, membrane computing, P system, Turing computability} } @article{Madhu:IJFCS:Probabilistic_R:03, author={Mutyam Madhu}, title={Probabilistic Rewriting {P} systems}, journal={International Journal of Foundations of Computer Science}, year={2003}, month={February}, volume={14}, number={1}, pages={157--166}, abstract={In this paper we define a variant of P systems, namely, probabilistic rewriting P systems, where the selection of rewriting rules is probabilistic. We show that, with non-zero cut-point, probabilistic rewriting P systems with/without priorities generate only finite languages, but with zero cut/point and without priorities, probabilistic rewriting P systems of degree 1 characterize the family of languages generated by matrix grammars. We also prove that probabilistic rewriting P systems of degree 1 with zero cut-point and priorities characterize recursively enumerable languages.} } @article{Madhu:IJCM:Class_P_automata:2003, author={Mutyam Madhu and Kamala Krithivasan}, title={On a Class of {P} Automata}, journal={International Journal of Computer Mathematics}, year={2003}, month={September}, volume={80}, number={9}, pages={1111--1120}, abstract={In this paper, we propose a class of P automata in which each membrane has a state, like in tissue P systems [5], and the computation starts at some initial state and ends in a final state. Unlike the automaton considered in [2], where rules are used in sequential manner, here we consider a variant such that the rules can be applied in maximal mode (as defined in tissue P systems). We show that P automata characterize the recursively enumerable sets of vectors of natural numbers.}, keywords={P Systems, Tissue P Systems, One-way P Automata, Parikh Mapping, Matrix Grammar, Recursively Enumerable Languages} } @article{Sabadini:ENTCS:2003, author={N. Sabadini and R.F.C. Walters}, title={Hierarchical automata and P systems}, journal={Electronic Notes in Theoretical Computer Science}, year={2003}, number={78}, pages={1--15} } @article{Sosik:NC:Computational_power_cell_division:2003, author={Petr Sos{\'i}k}, title={The computational power of cell division in {P} systems: Beating down parallel computers?}, journal={Natural Computing}, year={2003}, month={August}, volume={2}, number={3}, pages={287--298}, abstract={We study the computational power of cell division operations in the formal framework of P systems, a mathematical model of cell-like membrane structure with regulated transport of objects (molecules) through membranes. We show that a uniform family of P systems with active membranes and 2-division is able to solve the well-known PSPACE-complete problem QBF in linear time. This result implies that such a family of P systems modelling cell division is at least as powerful as so-called Second Machine Class computers. The Second Machine Class, containing most of the fundamental parallel computer models such as parallel RAM machines of types SIMD and MIMD, vector machines and others, is characterized by using an exponential amount of resources (processing units) with respect to the computing time.}, keywords={P system, Second Machine Class, membrane computing} } @article{Kefala:BioSystems:Simulation_and_:03, author={Petros Kefalas and G. Eleftherakis and Mike Holcombe and Marian Gheorghe}, title={Simulation and verification of {P} systems through communicating {X}-machines}, journal={BioSystems}, year={2003}, month={July}, volume={70}, number={2}, pages={135--148}, abstract={The aim of this paper is to prove the suitability of a parallel distributed computational model, communicating X-machines, to simulate in a natural way a well established model of molecular computation, P systems, and to present some further benefits of the approach allowing us to check for some formal properties. A set of rules to transform any P system with symbol-objects into a communicating X-machine model is presented and a variation of temporal logic for X-machines is briefly discussed, which facilitates model checking of desired properties of the system. Finally, the benefits resulting from the transformation are discussed.} } @article{Ceterchi:NC:Array_Rewriting:2003, author={Rodica Ceterchi and Mutyam Madhu and Gheorghe P{\u a}un and K.G. Subramanian}, title={Array-rewriting {P} systems}, journal={Natural Computing}, year={2003}, month={August}, volume={2}, number={3}, pages={229 - 249}, abstract={We consider array languages (sets of pictures consisting of symbols placed in the lattice points of the 2D grid) and the possibility to handle them with P systems. After proving binary normal forms for array matrix grammars (which, even in the case when no appearance checking is used, are known to generate the array languages of arbitrary array grammars), we prove that the P systems with context-free rules (with three membranes and no control on the communication or the use of rules) are computationally universal, able to generate all computable array languages. Some open problems are also formulated.}, keywords={P system, Turing computability, array languages, matrix grammar, membrane computing} } @article{Krishna:TCS:Breaking_DES:2003, author={Shankara Narayanan Krishna and Raghavan Rama}, title={Breaking {DES} Using {P} systems}, journal={Theoretical Computer Science}, year={2003}, month={April}, volume={299}, number={1-3}, pages={495--508}, abstract={Membrane systems, also called P systems, were introduced by Gh. Paun, as a new class of biologically inspired distributed computing models. Several variants of P systems were already shown to be computationally universal. One of these variants, introduced in Gh. Paun (J. Automata Languages Combin. 6 (1) (2001) 75), is able to solve SAT in linear time. In this paper, we show how this class of P systems (with membrane division) can theoretically break the most widely used cryptosystem, DES. We prove that given an arbitrary (plain-text, cipher-text) pair, one can recover the DES key in linear time with respect to the length of the key.}, keywords={DES, P systems, membrane computing} } @article{Leporati:Simulating_the_Fredkin_Gate:JUCS:2004, author={Alberto Leporati and Claudio Zandron and Giancarlo Mauri}, title={Simulating the {F}redkin {G}ate with Energy-Based {P} systems}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={600--619}, abstract={Reversibility plays a fundamental role when the possibility to perform computations with minimal energy dissipation is considered. Many papers on reversible computation have appeared in literature, the most famous of which is certainly the work of Bennett on (universal) reversible Turing machines. Here we consider the work of Fredkin and Toffoli on conservative logic, which is a mathematical model that allows to describe computations which reflect some properties of microdynamical laws of physics, such as reversibility and conservation of the internal energy of the physical system used to perform the computations. The model is based upon the Fredkin gate, a reversible and 'conservative' (according to a definition given by Fredkin and Toffoli) three-input/three-output boolean gate. In this paper we introduce energy based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. Moreover, we show how energy-based P systems can be used to simulate the Fredkin gate. The proposed P systems that perform the simulations turn out to be themselves reversible and conservative.}, keywords={Energy-based P systems, Fredkin gate, conservative logic, reversibility, conservativeness} } @article{Cordon-Franco:Note_Complexity_Measures:JUCS:2004, author={Andr{\'e}s Cord{\'o}n-Franco and Fernando Sancho-Caparrini}, title={A Note on Complexity Measures for Probabilistic {P} systems}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={559--568}, abstract={In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To this end, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.}, keywords={P systems, Entropy, Natural Computing} } @article{CordonFranco:NGC:Prolog_simulator:2004, author={Andr{\'e}s Cord{\'o}n-Franco and Miguel A. Guti{\'e}rrez-Naranjo and Mario J. P{\'e}rez-Jim{\'e}nez and Fernando Sancho-Caparrini}, title={A {P}rolog Simulator for Deterministic {P} systems with Active Membranes}, journal={New Generation Computing}, year={2004}, month={August}, volume={22}, number={4}, pages={349--363}, abstract={In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in each step of the evolution as literals of an appropriate language of first order logic. We provide a Prolog program to simulate the evolution of these P systems and present some auxiliary tools to simulate the evolution of a P system with active membranes using 2-division which solves the SAT problem following the techniques presented in Reference 10).}, keywords={Logic Programming, Membrane Computing, Simulation, Prolog, SAT-problem.} } @article{Alhazov:IPL:SymbolSet:IPL2006, author = {Artiom Alhazov}, title = {{P} Systems without Multiplicities of Symbol-Objects}, journal = {Information Processing Letters}, volume = {100}, number = {3}, year = {2006}, month = {November}, abstract = {In this paper we investigate P systems whose compartments contain sets of symbol-objects rather than multisets of objects as it is common in membrane computing. If the number of membranes cannot grow, then in this framework we can characterize exactly the regular languages. If membrane creation or membrane division is allowed, then the Parikh sets of recursively enumerable languages can be generated. The last result also implies the universality of P systems with active membranes (with multisets of symbol-objects) without polarizations.}, keywords = {Formal languages, Theory of computation, Distributed computing, Parallel processing, Membrane systems, Turing computability}, url = {http://dx.doi.org/10.1016/j.ipl.2005.01.017}, } @article{Alhazov:DECP:JUCS2004, author = {Artiom Alhazov}, title = {On Determinism of Evolution-Communication {P} systems}, journal = {Journal of Universal Computer Science}, year = {2004}, month = {May}, volume = {10}, number = {5}, pages = {502--508}, abstract = {It is commonly believed that a significant part of the computational power of membrane systems comes from their inherent non-determinism. Recently, R. Freund and Gh. P{\u a}un have considered deterministic P systems, and formulated the general question whether the computing (generative) capacity of non-deterministic P systems is strictly larger than the (accepting) capacity of their deterministic counterpart. In this paper, we study the computational power of deterministic P systems in the evolution-communication framework. It is known that in the generative case, two membranes are enough for universality. For the deterministic systems, we obtain the universality with three membranes, leaving the original problem open.}, keywords = {Membrane computing, P system, Determinism, Computational completeness}, url = {http://www.jucs.org/jucs_10_5/on_determinism_of_evolution}, } @article{Alhazov:MinECP:NGC2004, author = {Artiom Alhazov}, title = {Minimizing Evolution-Communication {P} Systems and Automata}, journal = {New Generation Computing}, year = {2004}, month = {August}, volume = {22}, number = {4}, pages = {299--310}, abstract = {Evolution-communication P systems are a variant of P systems allowing both rewriting rules and symport/antiport rules, thus having separated the rewriting and the communication. The purpose of this paper is to solve an open problem stated in Reference 1), namely generating the family of Turing computable sets of vectors of natural numbers instead of the family of Turing computable sets of natural numbers. The same construction also reduces the 3-membrane non-cooperative case and the 2-membrane 1-catalyst case to the 2-membrane non-cooperative case. Also, EC P automata are introduced and it is proved that 2-membrane EC P automata with a promoter can accept all recursively enumerable languages. Finally, a definition of an extended system is given, and its universality is proved using the rules of more restricted types.}, keywords = {Membrane Computing, EC P Systems, EC P Automata, Turing Computability.}, url = {http://www.springerlink.com/content/b5707359hp67p8w2/}, } @article{Alhazov.Pan:Polarizationless:Grammars2004, author = {Artiom Alhazov and Linqiang Pan}, title = {Polarizationless {P} Systems with Active Membranes}, journal = {Grammars}, year = {2004}, volume = {7}, pages = {141--159}, abstract = {The subject of this paper is the continuation of the studies of P systems with active membranes without polarizations with the label-changing capacity of some rules. Rewriting and communication rules that do not change membrane labels can be applied either sequentially or in a maximally parallel way. We consider several classes of P systems and study their generative power. Particularly interesting, P systems with only evolution rules used sequentially and changing labels compute exactly the Parikh sets of matrix languages; the universality is reached by P systems with evolution rules and communication rules used sequentially. By direct constructions we also prove that SAT can be solved in linear time by systems with evolution rules changing labels communication, and membrane division. Several open problems are also formulated.}, eprint = {http://aartiom.50webs.com/articles/RelabN607.pdf}, url = {http://grlmc-dfilrom.urv.cat/1stschool_artiom.asp}, } @article{Alhazov.etal:Trading_Polarizations:AI2004, author = {Artiom Alhazov and Linqiang Pan and {\relax Gh}eorghe P{\u a}un}, title = {Trading Polarizations for Labels in {P} Systems with Active Membranes}, journal = {Acta Informatica}, year = {2004}, month = {December}, volume = {41}, number = {2-3}, pages = {111--144}, abstract = {This paper addresses the problem of removing the polarization of membranes from P systems with active membranes - and this is achieved by allowing the change of membrane labels by means of communication rules or by membrane dividing rules. As consequences of these results we obtain the universality of P systems with active membranes which are allowed to change the labels of membranes, but do not use polarizations. Universality results are easily obtained also by direct proofs. By direct constructions, we also prove that SAT can be solved in linear time by systems without polarizations and with label changing possibilities. If non-elementary membranes can be divided, then SAT can be solved in linear time without using polarizations and label changing. Several open problems are also formulated.}, url = {http://dx.doi.org/10.1007/s00236-004-0153-z}, } @article{Calude:BioSystems:Bio-steps_beyond_Turing:2004, author={Cristian S. Calude and Gheorghe P{\u a}un}, title={Bio-steps beyond {T}uring}, journal={BioSystems}, year={2004}, month={November}, volume={77}, number={1-3}, pages={175--194}, abstract={Are there �biologically computing agents� capable to compute Turing uncomputable functions? It is perhaps tempting to dismiss this question with a negative answer. Quite the opposite, for the first time in the literature on molecular computing we contend that the answer is not theoretically negative. Our results will be formulated in the language of membrane computing (P systems). Some mathematical results presented here are interesting in themselves. In contrast with most speed-up methods which are based on non-determinism, our results rest upon some universality results proved for deterministic P systems. These results will be used for building 'accelerated P systems'. In contrast with the case of Turing machines, acceleration is a part of the hardware (not a quality of the environment) and it is realised either by decreasing the size of 'reactors' or by speeding-up the communication channels. Consequently, two acceleration postulates of biological inspiration are introduced; each of them poses specific questions to biology. Finally, in a more speculative part of the paper, we will deal with Turing non-computability activity of the brain and possible forms of (extraterrestrial) intelligence.}, keywords={Turing; Bio-steps; P systems} } @article{Besozzi:NGC:Hierarchies_parallel:2004, author={Daniela Besozzi and Giancarlo Mauri and Claudio Zandron}, title={Hierarchies of Parallel Rewriting {P} Systems. A Survey}, journal={New Generation Computing}, year={2004}, month={August}, volume={22}, number={4}, pages={331--347}, abstract={The paper is about some families of rewriting P systems, where the application of evolution rules is extended from the classical sequential rewriting to the parallel one (as, for instance, in Lindenmayer systems). As a result, consistency problems for the communication of strings may arise. Three variants of parallel rewriting P systems (already present in the literature) are considered here, together with the strategies they use to face the communication problem, and some parallelism methods for string rewriting are defined. We give a survey of all known results about each variant and we state some relations among the three variants, thus establishing hierarchies of parallel rewriting P systems. Various open problems related to the subject are also presented.}, keywords={Membrane Computing, Parallel Rewriting, Lindenmayer System, Recursively Enumerable Language.} } @article{Fontana:Finding_the_Maximum_Element:JUCS:2004, author={Federico Fontana and Giuditta Franco}, title={Finding the Maximum Element Using {P} systems}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={567--580}, abstract={A nondeterministic, maximally parallel methodology for finding the maximum element in a set of numerical values is presented, suitable for being implemented on P systems. Several algorithms of maximum search are then developed for different types of such systems, namely using priorities, nested membranes and linked transport, and their performances are evaluated accordingly. The proposed solutions are expected to find application inside membrane models devoted to compute algorithmic procedures in which the greatest element in a data set must be found. Dynamic algorithms for DNA sequence alignment are an example of such procedures.}, keywords={Maximum value, P systems, Natural computing, Membrane computing} } @article{Arroyo:Simulating_Membrane_Systems:IJITA:2004, author={Fernando Arroyo and Carmen Luengo and Luis Fernandez and Luis F. de Mingo and Juan Castellanos}, title={Simulating membrane systems in digital computers}, journal={International Journal "Information Theories \& Applications"}, year={2004}, volume={11}, number={1}, pages={29--34}, abstract={Membrane Computing started with the analogy between dome processes produced inside the complex structure of living cells and computational processes. In the same way that in other branches of Natural Computing, the model is extracted from nature but it is not clear wether or not the model must come back to nature to be implemented. As in other cases in Natural Computing: Artificial Neural Networks, Genetic Algorithms, etc; the models have been implemented in digital computers. Hence some papers have been published considering inplementation of Membrane omputing in digital computers. This paper introduces an overview in the field of simulation in Membrane Computing.} } @article{Bernardini:NGC:Lang_generated:2004, author={Francesco Bernardini and Marian Gheorghe}, title={Languages Generated by {P} systems with Active Membranes}, journal={New Generation Computing}, year={2004}, month={August}, volume={22}, number={4}, pages={311--329}, abstract={We propose an alternative approach to generate languages by means of P systems: building up an appropriate representation for a string by means of a corresponding membrane structure and then generating the string by visiting the membrane structure according to a well-specified strategy. To this aim, we consider P systems with active membranes, allowing membrane creation or division or duplication and dissolution, where the output of a computation may be obtained either by visiting the tree associated with the membrane structure, or by following the traces of a specific object, called traveller, or sending out the objects. For each of these approaches, we provide characterizations of recursively enumerable languages based on P systems that use different sets of operations for modifying the membrane structure.}, keywords={Membrane Computing, P System, Recursively Enumerable Language.} } @article{Bernardini:Population_P_Systems:JUCS:2004, author={Francesco Bernardini and Marian Gheorghe}, title={Population {P} systems}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={509--539}, abstract={This paper introduces a notion of population P systems as a class of tissue P systems where the links between the cells can be modified by means of a specific set of bond making rules. As well as this, cell division rules which introduce new cells into the system, cell differentiation rules which change the set of rules that can be used inside of a cell, and cell death rules which remove cells from the system are also considered by introducing a particular notion of population P systems with active cells. The paper mainly reports universality results for the following models: (a) population P systems where cells are restricted to communicate only by means of the environment but never forming any bond; (b) population P systems with bond making rules with restricted communication rules; (c) population P systems possessing only the cell differentiation operation; and (d) population P systems equipped with cell division rules and bond making rules.}, keywords={Membrane computing, Cell bonding, Cell division, Cell differentiation, Turing computability} } @article{Ciobanu:NGC:P_Transducers:2004, author={Gabriel Ciobanu and Gheorghe P{\u a}un and Gheorghe Stefanescu}, title={{P} transducers}, journal={New Generation Computing}, year={2004}, note={To appear} } @article{Paun:BEATCS:Membrane_Computing_After_2BWMC:2004, author={Gheorghe P{\u a}un}, title={Membrane Computing (after the {Second} {Brainstorming} {Week}, {Sevilla}, February 2004)}, journal={Bulletin of the EATCS}, year={2004}, month={June}, abstract={We briefly present some of the ideas discussed and the results obtained during the Second Brainstorming Week on Membrane Computing, held in Sevilla at the beginning of February 2004. Detains can be found in the proceedings volume (whose contents is appened to these notes), available through the P page http://psystems.disco.unimib.it, maintained in Milano under the auspices of the European Molecular Computing Consortium, EMCC, or through the recently created membrane computing forum page, in Sevilla, at http://www.cs.us.es/gcn/foro.htm.} } @article{Paun:TCS:Membrane_division:2004, author={Gheorghe P{\u a}un and Yasuhiro Suzuki and Hiroshi Tanaka and Takashi Yokomori}, title={On the power of membrane division in {P} systems}, journal={Theoretical Computer Science}, year={2004}, month={September}, volume={324}, number={1}, pages={61--85}, abstract={First, we consider P systems with active membranes, hence with the possibility that the membranes can be divided, with non-cooperating evolution rules (the objects always evolve separately). These systems are known to be able to solve NP-complete problems in linear time. Here we give a normal form theorem for such systems: their computational universality is preserved even if only the elementary membranes are divided. The possibility of solving SAT in linear time is preserved only when non-elementary membranes may also be divided under the influence of objects in their region. Second, we consider a slight generalization, namely, we allow that a membrane can produce by division both a copy of itself and a copy of a membrane with a different label; again, only elementary membranes may be divided. In this case, we prove that the hierarchy on the maximal number of membranes present in the system collapses: three membranes at a time are sufficient in order to characterize the recursively enumerable sets of vectors of natural numbers. This result is optimal, two membranes are shown not to be sufficient. Third, we consider P systems with cooperating rules (several objects may evolve together). Making use of this powerful feature, we show that many NP-complete problems can be solved in linear time in a quite uniform way (by systems which are very similar to each other), using only elementary membranes division (and not further ingredients, such as electrical charges). The degree of cooperation is minimal: two objects at a time.}, keywords={Membrane computing; Recursively enumerable language; Universality; SAT problem} } @article{Nepomuceno:A_Java_Simulator:JUCS:2004, author={Isabel A. Nepomuceno-Chamorro}, title={A {J}ava Simulator for Membrane Computing}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={620--629}, abstract={Membrane Computing is a recent area of Natural Computing, a topic where much work has been done but still much remains to be done. There are some applications which have been developed in imperative languages, like C++, or in declaratives languages, as Prolog, working in the framework of P systems. In this paper, a software tool (called SimCM, from Spanish Simulador de Computaci{\'o}n con Membranas) for handling P systems is presented. The program can simulate basic transition P Systems where dissolution of membranes and priority rules are allowed. The software application is carried out in an imperative and object-oriented language - Java. We choose Java because it is a scalable and distributed language. Working with Java is the first step to cross the border between simulations and a distributed implementation able to capture the parallelism existing in the membrane computing area. This tool is a friendly application which allows us to follow the evolution of a P system easily and in a visual way. The program can be used to move the P system theory closer to the biologist and all the people who wants to learn and understand how this model works.}, keywords={P system, Parallelism, Simulation, Java} } @article{Inouye:WSEATBM:2004, author={J. Inouye and P.P. Dey}, title={Membranous Filter Sort}, journal={WSEA Transactions on Biology and Medicine}, year={2004}, month={October}, volume={1}, number={4}, note={ISSN: 1109-9518} } @article{Dersanambika:IJCM:Contextual_array_PS:2004, author={K.S. Dersanambika and Kamala Krithivasan}, title={Contextual Array {P} systems}, journal={International Journal of Computer Mathematics}, year={2004}, month={August}, volume={81}, number={8}, pages={955--969}, abstract={We define external and internal array contextual P systems, which generate rectangular arrays. We also introduce external array contextual P systems with erased contexts. Some properties of these systems are discussed. We obtain the relation between external array contextual P systems and external array contextual grammars with regular control.}, keywords={Contextual Grammars, P Systems, Array Grammars, Regular Control, Contextual P Systems} } @article{Cienciala:JCST:2004, author={L. Cienciala and L. Ciencialova}, title={Membrane automata with priorities}, journal={Journal of Computer Science and Technology}, year={2004}, volume={19}, number={1}, pages={89--97} } @article{Cienciala2:JCST:2004, author={L. Cienciala and L. Ciencialova}, title={Membrane automata with priorities}, journal={Journal of Computer Science and Technology}, year={2004}, volume={19}, number={1}, pages={89--97} } @article{Pan:Active_Membranes_Separation_Rules:JUCS:2004, author={Linqiang Pan and Tseren Onolt Ishdorj}, title={{P} systems with Active Membranes and Separation Rules}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={630--649}, abstract={The P systems are a class of distributed parallel computing devices of a biochemical type. In this paper, a new definition of separation rules in P systems with active membranes is given. Under the new definition, the efficiency and universality of P systems with active membranes and separation rules instead of division rules are investigated.}, keywords={Natural computing, Membrane computing, Distributed computing} } @article{Cienciala:JCST:Membrane_automata:2004, author={Lud{\u e}k Cienciala and Lucie Ciencialov{\'a}}, title={Membrane automata with priorities}, journal={Journal of Computer Science and Technology}, year={2004}, month={January}, volume={19}, number={1}, pages={89--97}, note={Special issue on bioinformatics}, abstract={In this paper the one-way P automata with priorities are introduced. Such automata are P systems where the membranes are only allowed to consume objects from parent membranes, under the given conditions. The result of computation of these systems is the set of multiset sequences consumed by skin membrane into the system. The rules associated in some order with each membrane cannot modify any objects, they can only move them through membrane. We show that P automata with priorities and two membranes can accept every recursively enumerated language.}, keywords={P systems, membrane computing} } @article{Mutyam:TCS:improved_hier:2004, author={Madhu Mutyam}, title={Rewriting {P} systems: improved hierarchies}, journal={Theoretical Computer Science}, year={2004}, note={In press}, abstract={Generally, for proving universality results about rewriting P systems one considers matrix grammars in the strong binary normal form. Such grammars contain both matrices with rules used in the appearance checking mode and matrices without appearance checking rules. In the proofs of most of the universality theorems reported in the literature, appearance checking matrices are simulated by using only two membranes, while four membranes are used for simulating matrices without appearance checking rules. Thus, a way to improve these theorems is to diminish the number of membranes used for simulating matrices without appearance checking rules. In this paper we address this problem, and give first a general improved result about simulating matrix grammars without appearance checking: three membranes are shown to suffice. This result is then used to improve several universality results from various membrane computing papers, for instance, about P systems with replicated rewriting, with leftmost rewriting, with conditional communication, as well as for hybrid P systems with finite choice.}, keywords={P systems; Rewriting P systems; Recursively enumerable languages; Computational universality; Leftmost rewriting; Replicated rewriting; Matrix languages; Conditional communication; Penttonen normal form; Hybrid P systems} } @article{Mutyam:JUCS:Rewriting_tissue_PS:2004, author={Madhu Mutyam and Vaka Jaya Prakash and Kamala Krithivasan}, title={Rewriting tissue {P} systems}, journal={Journal of Universal Computer Science}, year={2004}, month={September}, volume={10}, number={9}, pages={1250--1271}, abstract={By considering string-objects and rewriting rules, we propose a variant of tissue P systems, namely, rewriting tissue P systems. We show the computational efficiency of rewriting tissue P systems by solving the Satisfiability and the Hamiltonian path problems in linear time. We study the computational capacity of rewriting tissue P systems and show that rewriting tissue P systems with at most two cells and four states are computationally universal. We also show the universality result of rewriting tissue P systems with at most one cell and five states. Finally we propose some new directions for future work.}, keywords={Tissue P systems, rewriting tissue P systems, computational universality, matrix grammars} } @article{Perez-Jimenez:Modelos_de_CCM:BSEMA:2004, author={Mario J. P{\'e}rez-Jim{\'e}nez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, title={Modelos de computacion celular con membranas}, journal={Boletin de la Sociedad Espa{\~n}ola de Matem{\'a}tica Aplicada}, year={2004}, month={September}, number={29}, pages={57--88} } @article{Perez-Jimenez:Packing_Items_into_Bins:JUCS:2004, author={Mario J. P{\'e}rez-Jim{\'e}nez and Francisco Jos{\'e} Romero-Campero}, title={An Efficient Family of {P} systems for Packing Items into Bins}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={650--670}, abstract={In this paper we present an effective solution to the Bin Paching problem using a family of recognizer P systems with active membranes. The analysis of the solution presented here will be done from the point of view of complexity classes. A CLIPS simulator for recognizer P systems is used to describe a session for an instance of Bin Packing, using a P system from the designed family.}, keywords={Membrane computing, Recognizer P systems, Complexity classes, Bin Packing problem, CLIPS} } @article{Cavaliere:Symport/Antiport_of_Rules:JUCS:2004, author={Matteo Cavaliere and Daniela Genova}, title={{P} systems with Symport/Antiport of Rules}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={540--558}, abstract={Moving 'instructions' instead of 'data' using transport mechanisms inspired by biology is the basic idea of the computing device presented in this paper. Specifically, we propose a new class of P systems that use both evolution rules and symport/antiport rules. The idea of this kind of systems is the following: during a computation, symbol-objects (the 'data') evolve using evolution rules, but they cannot be moved; on the other hand, the evolution rules (the 'instructions') can be moved across the membranes using classical symport/antiport rules. We present a number of results using different combinations of evolution rules (catalytic, non-cooperative) and the weight of the symport/antiport rules. In particular, we show that using non-cooperative rules and antiports of unbounded weight makes it possible to obtain at least the Parikh set of ET0L languages. On the other hand, using catalytic rules (one catalyst) and antiports of weight 2, these system become universal. Several open problems are also presented.}, keywords={Membrane computing, Communication, Evolution, P system, Symport, Antiport} } @article{Cavaliere:TCS:Evolution_observation:2004, author={Matteo Cavaliere and Peter Leupold}, title={Evolution and observation�a non-standard way to generate formal languages}, journal={Theoretical Computer Science}, year={2004}, month={August}, volume={321}, number={2-3}, pages={233-248}, abstract={In biology and chemistry a standard proceeding is to conduct an experiment, observe its progress, and then take the result of this observation as the final output. Inspired by this, we have introduced P/O systems (A. Alhazov, C. Mart{\'i}n-Vide, Gh. Pun, Pre-Proc. of the Workshop on Membrane Computing 2003, Tarrragona, Spain; http://pizarro.fll.urv.es/continguts/linguistica/proyecto/reports/wmc03.html), where languages are generated by multiset automata that observe the evolution of membrane systems. Now we apply this approach also to more classical devices of formal language theory. Namely, we use finite automata observing the derivations of grammars or of Lindenmayer systems. We define several modes of operation for grammar/observer systems. In two of these modes a context-free grammar (or even a locally commutative context-free grammar) with a finite automaton as observer suffices to generate any recursively enumerable language. In a third case, we obtain a class of languages between the context-free and context-sensitive ones.}, keywords={Formal languages; Evolution; Observation} } @article{Ionescu:Promoters/Inhibitors:JUCS:2004, author={Mihai Ionescu and Dragos Sburlan}, title={On {P} systems with Promoters/Inhibitors}, journal={Journal of Universal Computer Science}, year={2004}, month={May}, volume={10}, number={5}, pages={581--599}, abstract={This article shows how the computational universality can be reached using P systems with object rewriting non-cooperative rules, promoters/inhibitors at the level of rules, and only one catalyst. Both generative and accepting cases are studied. The theoretical issues presented are illustrated by several examples.}, keywords={P Systems, universality, promoters, inhibitors} } @article{Jonoska:FUND_INFORM:Tree_operations:2004, author={Nata{\u s}a Jonoska and Maurice Margenstern}, title={Tree operations in {P} systems and $\lambda$-calculus}, journal={Fundamenta Informaticae}, year={2004}, volume={59}, number={1}, pages={67--90}, abstract={In this paper we introduce a membrane system (named ?P systems) in which the computation is performed through certain operations on the tree structure of the membranes. The objects within the membranes play the role of catalysts for the operations. The result of the computation is the final configuration of the system. We show that ?P systems can simulate pure ?-calculus and so they have universal computational power. We also show that NP-complete problems can be solved in polynomial time in this way by showing that 3SAT is solvable in linear time with linear input.} } @article{Ibarra:TCS:Comput_Complexity_Mem_sys:2004, author={Oscar H. Ibarra}, title={On the computational complexity of membrane systems}, journal={Theoretical Computer Science}, year={2004}, month={June}, volume={320}, number={1}, pages={89--109}, abstract={We show how techniques in machine-based complexity can be used to analyze the complexity of membrane computing systems. We focus on catalytic syslems, communicating P systems, and systems with only symport/antiport rules, but our techniques are applicable to other P systems that are universal. We define space and time complexity measures and show hierarchies of complexity classes similar to well-known results concerning Turing machines and counter machines. We also show that the deterministic communicating P system simulating a deterministic counter machine in (Sosik (2002)) (Pre-Proc. of Workshop on Membrane Computing (WMC-CdeA2002), Curtea de Arges, Romania, 2002, pp. 371-382), (Sosik and Matysek (2002)) (Unconventional Models of Computation 2002, Lecture Notes in Computer Science, vol. 2509, Springer, Berlin, 2002, pp. 264-275.) can be constructed to have a fixed number of membranes, answering positively an open question in Sosik (2002), Sosik and Matysek (2002). We prove that reachability of extended configurations for symport/antiport systems (as well as for catalytic systems and communicating P systems) can be decided in nondeterministic log n space and, hence, in deterministic log2 n space or in polynomial time, improving the main result in Paun et al. (2002) (On the reachability problem for P systems with symport/antiport, 2002, submitted for publication.), We propose two equivalent systems that define languages (instead of multisets of objects): the first is a catalytic system language generator and the other is a communicating P system acceptor (or a symport/antiport system acceptor). These devices are universal and therefore can also be analyzed with respect to space and time complexity. Finally, we give a characterization of semilinear languages in terms of a restricted form of catalytic system language generator.}, keywords={acceptor, catalytic system, communicating P system, generator, membrane computing, reachability, semilinear, space bounded, symport/antiport system, time bounded} } @article{Ibarra:TCS:Membrane_hierarchy:2004, author={Oscar H. Ibarra}, title={On membrane hierarchy in {P} systems}, journal={Theoretical Computer Science}, year={2004}, note={In press}, abstract={We look at a restricted model of a communicating P system, called RCPS, whose environment does not contain any object initially. The system can expel objects into the environment but only expelled objects can be retrieved from the environment. Such a system is initially given an input a1i1�anin (with each ij representing the multiplicity of distinguished object ai, 1in) and is used as an acceptor. We show that RCPSs are equivalent to two-way multihead finite automata over bounded languages (i.e., subsets of a1*�an*, for some distinct symbols a1,�,an). We then show that there is an infinite hierarchy of RCPS's in terms of the number of membranes: For every r, there is an s>r and a unary language L accepted by an RCPS with s membranes that cannot be accepted by an RCPS with r membranes. This provides an answer to an open problem in (Membrane Computing: An Introduction, Springer, Berlin, 2002) which asks whether there is a nonuniversal model of a membrane computing system which induces an infinite hierarchy on the number of membranes. We also consider variants/generalizations of RCPSs, e.g, acceptors of languages; models that allow a 'polynomial bounded' supply of objects in the environment initially; models with tentacles, etc. We show that they also form an infinite hierarchy with respect to the number of membranes (or tentacles). The proof techniques can be used to obtain similar results for other restricted models of P systems, like symport/antiport systems.}, keywords={Membrane computing; Communicating P system; Counter machine; Two-way multihead finite automaton; Hierarchy; System with tentacles; Semilinear set} } @article{Ibarra:THEOR_COMPUT_SCI:Catalytic_P_systems:2004, author={Oscar H. Ibarra and Zhe Dang and Omer Egecioglu}, title={Catalytic {P} systems, semilinear sets, and vector addition systems}, journal={Theoretical Computer Science}, year={2004}, month={January}, volume={312}, number={2-3}, pages={379--399}, note={A short version of this paper (without proofs) was presented at the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003). This research was supported in part by NSF Grants IIS-0101134 and CCR02-08595.}, abstract={We look at 1-region membrane computing systems which only use rules of the form Ca -> Cv, where C is a catalyst, a is a noncatalyst, and v is a (possibly null) string of noncatalysts. There are no rules of the form a -> v. Thus, we can think of these systems as 'purely' catalytic. We consider two types: (1) when the initial configuration contains only one catalyst, and (2) when the initial configuration contains multiple catalysts. We show that systems of the first type are equivalent to communication-free Petri nets, which are also equivalent to commutative context-free grammars. They define precisely the semilinear sets. This partially answers an open question (in: WMC-CdeA'02, Lecture Notes in Computer Science, vol. 2597, Springer, Berlin, 2003, pp. 400�409; Computationally universal P systems without priorities: two catalysts are sufficient, available at http://psystems.disco.unimib.it, 2003). Systems of the second type define exactly the recursively enumerable sets of tuples (i.e., Turing machine computable). We also study an extended model where the rules are of the form q: (p,Ca -> Cv) (where q and p are states), i.e., the application of the rules is guided by a finite-state control. For this generalized model, type (1) as well as type (2) with some restriction correspond to vector addition systems. Finally, we briefly investigate the closure properties of catalytic systems.}, keywords={Catalytic system, Membrane computing, Reachability problem, Semilinear set, Vector addition system} } @article{Frisco:THEOR_COMPUT_SCI:The_Conformon-P:04, author={Pierluigi Frisco}, title={The {Conformon-P System}: A Molecular and Cell Biology-Inspired Computability Model}, journal={Theoretical Computer Science}, year={2004}, month={January}, volume={312}, number={2-3}, pages={295--319}, abstract={A new theoretical computational model, called conformon-P system, based on simple and basic concepts inspired from a theoretical model of the living cell and membrane computing is presented. The computational power of it and of some natural variants are studied. Links with Petri nets, reversible computation, other interpretations and variants of the model are briefly outlined.}, keywords={DNA computing; Conformon; P system} } @article{Frisco:Acta_Inform:PSys_Simulat_Counter_Autom:2004, author={Pierluigi Frisco and Hendrik Jan Hoogeboom}, title={{P} systems with symport/antiport simulating counter automata}, journal={Acta Informatica}, year={2004}, month={December}, volume={41}, number={2-3}, pages={145--170}, abstract={The generative capability of several variants of P systems with symport/antiport is studied via the simulation of counter automata. This leads to the reduction of the complexity, expressed in number of membranes and weight of rules, of P systems generating recursively enumerable sets.} } @article{Freund:TCS:From, author={Rudolf Freund and Carlos Mart{\'i}n-Vide and Gheorghe P{\u a}un}, title={From regulated rewriting to computing with membranes: collapsing hierarchies}, journal={Theoretical Computer Science}, year={2004}, month={January}, volume={312}, number={2-3}, pages={143--188}, abstract={In addressing certain problems about membrane computing, a recent and active branch of natural computing, it first was necessary to address certain problems from the area of regulated rewriting. Thus, the present paper is a contribution to both these domains.A central problem in membrane computing is that of the hierarchy with respect to the number of membranes: Are systems with n + 1 membranes more powerful than systems with n membranes? Does the number of membranes induce an infinite hierarchy of the computed functions? Usually, when proving the universality of membrane systems (also called P systems), one starts from a matrix grammar and the number of membranes depends on the number of non-terminal symbols used by this grammar in the so-called appearance checking mode. We first prove that recursively enumerable languages can be generated by matrix grammars with only two non-terminal symbols being used in the appearance checking mode. The proofs of this fact and of several related results are based on a simulation of register machines by means of graph-controlled grammars.Then, we consider three classes of membrane systems, and in all the three cases the hierarchies with respect to the number of membranes are shown to collapse at level four: systems with four membranes are computationally universal (but we do not know whether or not this result is optimal).}, keywords={P system, graph-controlled grammar, matrix grammar, membrane computing, non-terminal complexity, programmed grammar, recursively enumerable language, register machine, regulated rewriting} } @article{Freund:TCS:Tissue_PS_channel_stat:2004, author={Rudolf Freund and Gheorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez}, title={Tissue {P} systems with channel states}, journal={Theoretical Computer Science}, year={2004}, note={In press}, abstract={We consider tissue-like P systems with states associated with the links (we call them synapses) between cells, controlling the passage of objects across the links. We investigate the computing power of such devices for the case of using�in a sequential manner�antiport rules of small weights. Systems with two cells are proved to be universal when having arbitrarily many states and minimal antiport rules, or one state and antiport rules of weight two. Also the systems with arbitrarily many cells, three states, and minimal antiport rules are universal. In contrast, the systems with one cell and any number of states and rules of any weight only compute Parikh sets of matrix languages (generated by matrix grammars without appearance checking); characterizations of Parikh images of matrix languages are obtained for such one-cell systems with antiport rules of a reduced weight.}, keywords={Matrix grammars; Membrane computing; P systems; States; Turing computability} } @article{Freund:TCS:Two_catalyst:2004, author={Rudolf Freund and Lila Kari and Marion Oswald and Petr Sos{\'i}k}, title={Computationally universal {P} systems without priorities: two catalysts are sufficient}, journal={Theoretical Computer Science}, year={2004}, note={In press}, abstract={The original model of P systems with symbol objects introduced by Paun was shown to be computationally universal, provided that catalysts and priorities of rules are used. By reduction via register machines Sosik´ and Freund proved that the priorities may be omitted from the model without loss of computational power. Freund, Oswald, and Sosik´ considered several variants of P systems with catalysts (but without priorities) and investigated the number of catalysts needed for these specific variants to be computationally universal. It was shown that for the classical model of P systems with the minimal number of two membranes the number of catalysts can be reduced from six to five; using the idea of final states the number of catalysts could even be reduced to four. In this paper we are able to reduce the number of catalysts again: two catalysts are already sufficient. For P systems with external output or extended P systems we even need only one membrane and two catalysts. For the (purely) catalytic systems considered by Ibarra only three catalysts are already enough.}, keywords={Membrane computing; P systems; Catalysts; Complexity; Universality} } @article{Freund:NGC:P_S_with_local_graph:2004, author={Rudolf Freund and Marion Oswald}, title={{P} systems with Local Graph Productions}, journal={New Generation Computing}, year={2004}, month={August}, volume={22}, number={4}, pages={365--375}, abstract={P systems (membrane systems) of various types so far mainly have been considered as computing devices working on multisets or strings. In this paper we investigate P systems with local graph productions generating weakly connected directed graphs. At least when equipped with a priority relation on the rules, such P systems can generate any recursively enumerable language of weakly connected directed graphs with only one membrane.}, keywords={Membrane Computing, Graph Grammar, Recursively Enumerable Language.} } @article{Krishna:NGC:Results_on_catalytic:2004, author={Shankara Narayanan Krishna and Andrei P{\u a}un}, title={Results on Catalytic and Evolution-Communication {P} systems}, journal={New Generation Computing}, year={2004}, month={August}, volume={22}, number={4}, pages={377--394}, abstract={In this paper we give several improved universality results for two important classes of P systems: P systems with catalysts and evolution-communication P systems. First, the result from Reference 14), stating that six catalysts ensure the universality, has been improved in two ways: using bistable catalysts and using moving catalysts. Specifically, the universality can be reached with one bistable catalyst and 2 usual catalysts (using five membranes), as well as with one moving catalyst and three membranes, or with two moving catalysts and only two membranes. The second part of the paper deals with evolution-communication P systems, and we also give improved universality results for this type of systems, in terms of the weight of symport/antiport rules, number of membranes, or number of catalysts.}, keywords={Membrane Computing, Register Machine, Matrix Grammar, P System.} } @article{Nishida:JCI:NP_Complete_Optimization:2004, author={Taishin Yasunobu Nishida}, title={An approximate algorithm for {NP}-complete optimization problems exploiting {P} systems}, journal={Journal of Cybernetics and Informatics}, year={2004}, volume={V}, pages={109--112} } @article{Besozzi:Soft_Computing:Sept:2005, author={D. Besozzi and E. Csuhaj-Varju and G. Mauri and C. Zandron}, title={On the power and size of extended gemmating P systems}, journal={Soft Computing}, year={2005}, month={September}, volume={9}, number={9}, pages={650-6}, abstract={In [3] P systems with gemmation of mobile membranes were examined. It was shown that (extended) systems with eight membranes are as powerful as the Turing machines. Moreover, it was proved that extended gemmating P systems with only pre-dynamical rules are still computationally complete: in this case nine membranes are needed to obtain this computational power. In this paper we improve the above results concerning the size bound of extended gemmating P systems, namely we prove that these systems with at most five membranes (with meta-priority relations and without communication rules) form a class of universal computing devices, while in the case of extended systems with only pre-dynamical rules six membranes are enough to determine any recursively enumerable language.}, keywords={Membrane Computing, Gemmation, Recursively Enumerable Language, Geffert Normal Form} } @article{Bernardini:Soft_Computing:Sept:2005, author={F. Bernardini and M. Gheorghe}, title={Cell communication in tissue P systems: universality results}, journal={Soft Computing}, year={2005}, month={September}, volume={9}, number={9}, pages={640-649}, abstract={We introduce an evolution-communication model for tissue P systems where communication rules are inspired by the general mechanism of cell communication based on signals and receptors: a multiset can enter a cell only in the presence of another multiset. Some basic variants of this model are also considered where communication is restricted either to be unidirectional or to use special multisets of objects called receptors. The universality for all these variants of tissue P systems is then proved by using two cells (three cells in the case of unidirectional communication) and rules of a minimal size.}, keywords={Membrane computing, Turing computability, Tissue} } @article{Bernardini:Almost_periodicity:FUND_INFORM:05, author={Francesco Bernardini and Marian Gheorghe and Vincenzo Manca}, title={On {P} systems and almost periodicity}, journal={Fundamenta Informaticae}, year={2005}, note={To appear} } @article{Paun:S_A_3_objects_are_universal:FUND_INFORM:05, author={Gheorghe P{\u a}un and Juan Pazos and Mario Jes{\'u}s P{\'e}rez-Jim{\'e}nez and Alfonso Rodriguez-Pat{\'o}n}, title={Symport/antiport {P} systems with three objects are universal}, journal={Fundamenta Informaticae}, year={2005}, note={To appear} } @article{Ardelean:Soft_Computing:Sept:2005, author={I.I. Ardelean and M. Cavaliere and D. Sburlan}, title={Computing using signals: from cells to P systems}, journal={Soft Computing}, year={2005}, month={September}, volume={9}, number={9}, pages={631-639}, abstract={In cell biology a fundamental topic is the study of how biological signals are managed by cells. Signals can arise from inside the cell or from the external environment and the correct answer to certain signals is essential for bacteria to survive in a certain environment. Starting from these biological motivations we consider a model of P systems where the computation is controlled by signals which move across the regions. In particular, we consider signals-based P systems where the symbol-objects cannot be moved and the evolution rules can be activated/inactivated using a finite number of signals (signal-promoters) moved across the membranes, differently from standard P systems using promoters, in our case signal-promoters cannot be created during the computation. After discussing the biological motivations we show how this model becomes universal when it uses one catalyst and a bounded number of signal-promoters. Also results concerning signals-based P systems using non cooperative rules together with several open problems are presented.}, keywords={Membrane Computing, Cell Biology, Turing Computability, L System} } @article{Ledesma:Soft_Computing:Sept:2005, author={L. Ledesma and D. Manrique and A. Rodriguez-Paton}, title={A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem}, journal={Soft Computing}, year={2005}, month={September}, volume={9}, number={9}, pages={679-685}, abstract={This paper describes a tissue P system for solving the Shortest Common Superstring Problem in linear time. This tissue P system is well suited for parallel and distributed implementation using a microfluidic device working with DNA strands. The approach is not based on the usual brute force generate/test technique applied in DNA computing, but it builds the space solution gradually. The possible solutions/superstrings are build step by step through the parallel distributed combination of strings using the overlapping concatenation operation. Moreover, the DNA microfluidic device solves the problem autonomously, without the need of external control or manipulation.}, keywords={Membrane computing, DNA computing, Microflow reactor, Shortest common superstring problem} } @article{Pan.Alhazov.Ishdorj:FurtherMemOps:Soft_Computing2005, author = {Linqiang Pan and Artiom Alhazov and {\relax Ts}eren-Onolt Isdorj}, title = {Further remarks on P systems with active membranes, separation, merging and release rules}, journal = {Soft Computing}, year = {2005}, month = {September}, volume = {9}, number = {9}, pages = {686-690}, abstract = {The P systems are a class of distributed parallel computing devices of a biochemical type. In this note we show that by using membrane separation to obtain exponential workspace, SAT problem can be solved in linear time in a uniform and confluent way by active P systems without polarizations. This improves some results already obtained by A. Alhazov, T.-O. Isdorj. A universality result related to membrane separation is also obtained.}, keywords = {Membrane computing, Turing computability, {SAT} problem}, url = {http://dx.doi.org/10.1007/s00500-004-0399-y}, } @article{Gutierrez-Naranjo:Soft_Computing:Sept:2005, author = {M.A. Guti{\'e}rrez-Naranjo and M.J. P{\'e}rez-Jim{\'e}nez and A. Riscos-N{\'u}{\~n}ez}, title = {A fast {P} system for finding a balanced 2-partition}, journal = {Soft Computing}, year = {2005}, month = {September}, volume = {9}, number = {9}, pages = {673-678}, abstract = {Numerical problems are not very frequently addressed in the P systems literature. In this paper we present an effective solution to the 2-Partition problem via a family of deterministic P systems with active membranes using 2-division. The design of this solution is a sequel of several previous works on other problems, mainly on the Subset-Sum and the Knapsack problems. Several improvements are introduced and explained.}, keywords = {Complexity class, Membrane computing, Active membranes, {NP}-Complete problem}, } @article{Cavaliere:Time_and_synchronization:FUND_INFORM:05, author={Matteo Cavaliere and S. Sburlan}, title={Time and synchronization in membrane systems}, journal={Fundamenta Informaticae}, year={2005}, note={To appear} } @article{Frisco:Soft_Computing:Sept:2005, author={P. Frisco}, title={About P systems with symport/antiport}, journal={Soft Computing}, year={2005}, month={September}, volume={9}, number={9}, pages={664-672}, abstract={It is proved that four membranes suffice to a variant of P systems with symport/antiport with maximal parallelism to generate all recursively enumerable sets of numbers. P systems with symport/antiport without maximal parallelism are also studied, considering two termination criteria.}, keywords={Membrane computing, Turing computability, Symport/Antiport, Counter automaton} } @article{Freund:Soft_Computing:Sept:2005, author={R. Freund and A. Paun}, title={P systems with active membranes and without polarizations}, journal={Soft Computing}, year={2005}, month={September}, volume={9}, number={9}, pages={657-663}, abstract={P systems with active membranes but without using electrical charges (polarizations) are shown to be complete for generating recursively enumerable string languages when working on string objects and using only rules with membrane transitions as well as rules with membrane dissolving and elementary membrane division, but also when using various other kinds of rules, even including a new type of rules allowing for membrane generation. In particular, allowing for changing membrane labels turns out to be a very powerful control feature.}, keywords={Membrane computing, Recursively enumerable language, Membrane polarization} } @article{Krishna:Further_results:FUND_INFORM:05, author={Shankara Narayanan Krishna and Raghavan Rama and H. Ramesh}, title={Further results on contextual/rewriting {P} systems}, journal={Fundamenta Informaticae}, year={2005}, note={To appear} } @article{Alhazov.etal:UnitEnergy:FI2006, author = {Artiom Alhazov and Rudolf Freund and Alberto Leporati and Marion Oswald and Claudio Zandron}, title = {(Tissue) {P} Systems with Unit Rules and Energy Assigned to Membranes}, journal = {Fundamenta Informaticae}, volume = {74}, number = {4}, year = {2006}, month = {December}, pages = {391--408}, abstract = {We introduce a new variant of membrane systems where the rules are directly assigned to membranes and, moreover every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We show that for systems working in the sequential mode with a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation we obtain a characterization of the family of Parikh sets of languages generated by context-free matrix grammars. On the other hand when using the maximally parallel mode, we do not need a priority relation to obtain computational completeness. Finally, we introduce the corresponding model of tissue P systems with energy assigned to the membrane of each cell and objects moving from one cell to another one in the environment as well as being able to change the energy of a cell when entering or leaving the cell. In each derivation step only one object may pass through the membrane of each cell. When using priorities on the rules in the sequential mode (where in each derivation step only one cell is affected) as well as without priorities in the maximally parallel mode (where in each derivation step all cells possible are affected) we again obtain computational completeness, whereas without priorities on the rules in the sequential mode we only get a characterization of the family of Parikh sets of languages generated by context-free matrix grammars.}, keywords = {computational completeness, matrix grammars, membrane computing, P systems}, url = {http://iospress.metapress.com/content/5v45rcedw5rfyvnv/}, } @article{Leporati:Reversible_P_systems:FI:2006, author={A. Leporati and C. Zandron and G. Mauri}, title={Reversible {P} systems to simulate Fredkin circuits}, journal={Fundamenta Informaticae}, year={2006}, volume={74}, number={4}, pages={529--548} } @article{Obtulowicz:IJFCS:17:1:F2006, author={Adam Obtulowicz}, title={Gandy's principles for mechanisms and membrane computing}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={167-181}, abstract={The interconnections between membrane computing [9,11] and Gandy's principles for mechanisms in [3] are discussed. The embedding of the classes of hereditary finite sets (used to formulate Gandy's principles) into the class of abstract membrane systems is shown. A concept of a hereditary finite multiset is introduced as a special case of hereditary finite sets and then a representation of finite abstract membrane systems by hereditary finite multisets is presented. In this framework, a counterpart of the idea of reassemblance of hereditary finite sets is obtained for membrane systems.}, keywords={Membrane computing, hereditary finite sets, reassemblance} } @article{Leporati:IJFCS:17:1:F2006, author={Alberto Leporati and Claudio Zandron and Miguel A. Guti{\'e}rrez-Naranjo}, title={{P} systems with input in binary form}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={127-146}, abstract={Current P systems which solve NP-complete numerical problems represent the instances of the problems in unary notation. However, in classical complexity theory, based upon Turing machines, switching from binary to unary encoded instances generally corresponds to simplify the problem. In this paper we show that, when working with P systems, we can assume without loss of generality that instances are expressed in binary notation. More precisely, we propose a simple method to encode binary numbers using multisets, and a family of P systems which transforms such multisets into the usual unary notation. Such a family could thus be composed with the unary P systems currently proposed in the literature to obtain (uniform) families of P systems which solve NP-complete numerical problems with instances encoded in binary notation. We introduce also a framework which can be used to design uniform families of P systems which solve NP-complete problems (both numerical and non-numerical) working directly on binary encoded instances, i.e., without first transforming them to unary notation. We illustrate our framework by designing a family of P systems which solves the 3-SAT problem. Next, we discuss the modifications needed to obtain a family of P systems which solves the PARTITION numerical problem.}, keywords={Membrane computing, P systems, PARTITION, 3-SAT} } @article{Alhazov.etal:tCarpet:IJFCS2006, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald}, title = {Cell/Symbol Complexity of Tissue {P} Systems with Symport/Antiport Rules}, journal = {International Journal of Foundations of Computer Science}, year = {2006}, month = {February}, volume = {17}, number = {1}, pages = {3-25}, abstract = {We consider tissue P systems with symport/antiport rules and investigate their computational power when using only a (very) small number of symbols and cells. Even when using only one symbol, we need at most six (seven when allowing only one channel between a cell and the environment) cells to generate any recursively enumerable set of natural numbers. On the other hand, with only one cell we can only generate regular sets when using one channel with the environment whereas one cell with two channels between the cell and the environment obtains computational completeness with five symbols. Between these extreme cases of one symbol and one cell respectively, there seems to be a trade-off between the number of cells and the number of symbols. For example, for the case of tissue P systems with two channels between a cell and the environment we show that computational completeness can be obtained with two cells and three symbols as well as with three cells and two symbols, respectively. Moreover we also show that some variants of tissue P systems characterize the families of finite or regular sets of natural numbers.}, keywords = {Membrane computing, antiport rules, cells descriptional complexity, tissue P systems, universality}, url = {http://dx.doi.org/10.1142/S012905410600367X}, } @article{Pescini:IJFCS:17:1:F2006, author={Dario Pescini and Daniela Besozzi and Giancarlo Mauri and Claudio Zandron}, title={Dynamical probabilistic {P} systems}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={183-204}, abstract={Dynamical probabilistic P systems are discrete, stochastic, and parallel devices, where the probability values associated with the rules change during the evolution of the system. These systems are proposed as a novel approach to the analysis and simulation of the behavior of complex systems. We introduce all necessary definitions of these systems and of their dynamical aspects, we describe the functioning of the parallel and stochastic algorithm used in computer simulation, and evaluate its time complexity. Finally, we show some applications of dynamical probabilistic P systems for the investigation of the dynamics of the Lotka-Volterra system and of metapopulation systems.}, keywords={P system, dynamical system, stochastic process, metapopulation} } @article{Sburlan:IJFCS:17:1:F2006, author={Dragos Sburlan}, title={Further results on {P} systems with promoters/inhibitors}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={205-221}, abstract={This paper presents several results regarding P systems with non-cooperative rules and promoters/inhibitors at the level of rules. For the class of P systems using inhibitors, generating families of sets of vectors of numbers, a characterization of the family of Parikh sets of ET0L languages is shown. In the case of P systems with non-cooperative promoted rules even if an upper bound was not given, the inclusion of the family PsET0L was proved. Moreover, a characterization of such systems by means of a particular form of random context grammars, therefore a sequential formal device, is proposed.}, keywords={P Systems, promoters, inhibitors, random context} } @article{Bernardini:TCS:2006_, author={F. Bernardini and M. Gheorghe and N. Krasnogor}, title={Population {P} systems and quorum sensing in bacteria}, journal={Theoretical Computer Science}, year={2006}, note={¿?} } @article{Ciobanu:IJFCS:17:1:F2006, author={Gabriel Ciobanu and Mihai Gontineac}, title={Mealy multiset automata}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={111-126}, abstract={In this paper we introduce and study Mealy multiset automata, presenting some useful properties of multisets and comparing various approaches. We present the notions of bisimulation, observability, and behavior for Mealy multiset automata. We give a characterization of the bisimulation relation between two Mealy multiset automata, and a result relating their general behavior and sequential behavior. We define cascade and direct product of Mealy multiset automata. Then we introduce Mealy membrane automata corresponding to elementary P systems.}, keywords={Mealy automata, multisets, bisimulation, membranes systems} } @article{Chen:Handling_languages_with:ROMJIST:2006, author={H. Chen and T.-O. Ishdorj and Gh. Paun and M.J. Perez-Jimenez}, title={Handling languages with spiking neural P systems with extended rules}, journal={Romanian Journal of Information Science and Technology}, year={2006}, note={Accepted} } @article{Chen:Handling, author={H. Chen and T.-O. Ishdorj and Gh. Paun and M.J. Perez-Jimenez}, title={Handling languages with spiking neural P systems with extended rules}, journal={Romanian Journal of Information Science and Technology}, year={2006}, volume={9}, number={3}, pages={151--162} } @article{Subramanian:On, author={K.G. Subramanian and S. Hemalatha and C. Sri Hari Nagore and M. Margenstern}, title={On the power of P systems with parallel rewriting and conditional communication}, journal={Romanian Journal of Information Science and Technology}, year={2006}, note={Accepted} } @article{Bianco:IJFCS:17:1:F2006, author={Luca Bianco and Federico Fontana And Vincenzo Manca}, title={{P} systems with reaction maps}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={27-48}, abstract={Some recent types of membrane systems have shown their potential in the modelling of specific processes governing biological cell behavior. These models represent the cell as a huge and complex dynamical system in which quantitative aspects, such as biochemical concentrations, must be related to the discrete informational nature of the DNA and to the function of the organelles living in the cytosol. In an effort to compute dynamical (especially oscillatory) phenomena-so far mostly treated using differential mathematical tools-by means of rewriting rules, we have enriched a known family of membrane systems (P systems), with rules that are applied proportionally to the values expressed by real functions called reaction maps. Such maps are designed to model the dynamic behavior of a biochemical phenomenon and their formalization is best worked out inside a family of P systems called PB systems. The overall rule activity is controlled by an algorithm that guarantees the system to evolve consistently with the available resources (i.e., objects). Though radically different, PB systems with reaction maps exhibit very interesting, often similar dynamic behavior as compared to systems of differential equations. Successful simulations of the Lotka-Volterra population dynamics, the Brusselator, and the Protein Kinase C activation foster potential applications of these systems in computational systems biology.}, keywords={Membrane computing, dynamical systems modelling, computational systems biology} } @article{Cardelli:IJFCS:17:1:F2006, author={Luca Cardelli and Gheorghe Paun}, title={An universality result for a (mem)brane calculus based on mate/drip operations}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={49-68}, abstract={Operations with membranes are essential both in brane calculi and in membrane computing. In this paper we take four basic operations from brane calculi, pino, exo, mate, drip, we express them in terms of the membrane computing formalism, and then we investigate the computing power of the P systems using the mate, drip operations as unique evolution rules. All operations are controlled by - and make evolve - multisets of protein-objects embedded in the membranes themselves (not contained in the compartments of the cell, as standard in membrane computing all compartments delimited by membranes are here empty). Somewhat surprisingly, for systems which use the mate, drip operations we obtain the Turing completeness. The power of P systems based on other operations remains to be investigated.}, keywords={Brane calculi, membrane computing, universality, matrix grammar} } @article{Cavaliere:IJFCS:17:1:F2006, author={Matteo Cavaliere and Vincenzo Deufemia}, title={Further results on time-free {P} systems}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={69-89}, abstract={Membrane systems (currently called P systems) are parallel computing devices inspired by the structure and the functioning of living cells. A standard feature of P systems is that each rule is executed in exactly one time unit. Actually, in living cells different chemical reactions might take different times to be executed moreover, it might be hard to know precisely such time of execution. For this reason, in [7] two models of P systems (time-free and clock-free P systems) have been defined and investigated, where the time of execution of the rules is arbitrary and the output produced by the system is always the same, independently of this time. Preliminary results concerning time-free and clock-free P system have been obtained in [6, 7, 8]. In this paper we continue these investigations by considering different combinations of possible ingredients. In particular, we present the universality of time-free P systems using bi-stable catalysts. Then, we prove that this result implies that is not possible to decide whether an arbitrary bi-stable catalytic P system is time-free. We present several results about time-free evolution-communication P systems, where the computation is a mixed application of evolution and symport/antiport rules. In this case we obtain the universality even by using non-cooperative evolution rules and antiports of weight one. Finally, we formulate several open problems.}, keywords={Membrane systems, decidability, time-free system, universality} } @article{Muskulus:IJFCS:17:1:F2006, author={Michael Muskulus and Robert Brijder}, title={Complexity of bio-computation: symbolic dynamics in membrane systems}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={147-165}, abstract={We discuss aspects of biological relevance to the modelling of bio-computation in a multiset rewriting system context: turnover, robustness against perturbations, and the dataflow programming paradigm. The systems under consideration are maximally parallel and asynchronous parallel membrane systems, the latter corresponding to computation in which the notion of time is operationally meaningless. A natural geometrical setting which seems promising for the study of computational processes in general multiset rewriting systems is presented. Configuration space corresponds to a subset of the lattice N sub 0 super d, n, d, and state transitions correspond to vector addition. The similarities and differences with Vector Addition Systems and Petri nets are discussed. Symbolic dynamics are introduced on special partitions of configuration space and we indicate different notions of complexity for membrane systems based on this and related concepts such as graph complexity and minimal automata. Some examples of synchronized, pipelined dataflow computations are given and decompositions into functional subunits are briefly commented on.}, keywords={Membrane systems, vector addition systems, symbolic dynamics, dataflow computation, geometry of computation, automata decomposition, computational mechanics, robust bio-computation} } @article{Ceterchi:IJFCS:17:1:F2006, author={Rodica Ceterchi and Mario J. P{\'U}rez-Jim{\'U}nez}, title={On simulating a class of parallel architectures}, journal={International Journal of Foundations of Computer Science}, year={2006}, month={February}, volume={17}, number={1}, pages={91-110}, abstract={The purpose of this paper is twofold. On one hand, we introduce the concept of P system with dynamic communication graphs in its full generality, independent of applications. On the other hand, we illustrate one application of it to the simulation of a class of parallel architectures. In this last direction we extend previous work concerned with the simulation of particular architectures.}, keywords={Membrane computing, parallel architectures, dynamic communication, graphs} } @article{Freund:Pcolonies:IJCM:2006, author={Rudolf Freund and Marion Oswald}, title={P colonies and prescribed teams}, journal={Intern. J. Computer Math.}, year={2006} } @article{Krishna:TCS:2006_, author={S.N. Krishna}, title={Universality results for a brane calculus}, journal={Theoretical Computer Science}, year={2006}, note={¿?} } @article{Hemalatha:Array-rewriting:RMSLNS:2007, author={D. Hemalatha and K.S. Dersanambika and K.G. Subramanian and C. Sri Hari Nagore}, title={Array-rewriting P systems with conditional communication}, journal={Ramanujan Math. Soc. Lecture Notes Series}, year={2007}, number={3}, pages={155--160} } @article{Paun:Spiking_neural_P_systems:EATCS:2007, author={Gh. Paun}, title={Spiking neural {P} systems. {A} tutorial}, journal={Bulletin of the EATCS}, year={2007}, month={February} } @article{Krithivasan:A, author={K. Krithivasan}, title={A glimpse of membrane computing}, journal={Ramanujan Math. Soc. Lecture Notes Series}, year={2007}, number={3}, pages={49--61} } @article{Cienciala:On_the_power_of:IJFCS:2007, author={L. Cienciala and L. Ciencialova and P. Frisco and P. Sosik}, title={On the power of deterministic and sequential communicating {P} systems}, journal={International Journal of Foundations of Computer Science}, year={2007}, volume={18}, number={2}, pages={415--431} } @article{Mutyam:Tissue:RMSLNS:2007, author={M. Mutyam and K. Krithivasan}, title={Tissue P systems with leftmost derivation}, journal={Ramanujan Math. Soc. Lecture Notes Series}, year={2007}, number={3}, pages={187--196} } @article{Andrei:A_rewriting_logic:TCS:2007, author={O. Andrei and G. Ciobanu and D. Lucanu}, title={A rewriting logic framework for operational semantics of membrane systems}, journal={Theoretical Computer Science}, year={2007}, volume={373}, number={3}, pages={163--181} } @article{Frisco:From, author={P. Frisco}, title={From molecular computing to modelling with conformons and computing by observation}, journal={Ramanujan Math. Soc. Lecture Notes Series}, year={2007}, number={3}, pages={85--101} } @article{Krishna:On, author={S.N. Krishna}, title={On the efficiency of a variant of P systems with mobile membranes}, journal={Ramanujan Math. Soc. Lecture Notes Series}, year={2007}, number={3}, pages={171--178} } @article{Krishna:An, author={S.N. Krishna and R. Rama}, title={An infinite hierarchy for some variants of P systems}, journal={Ramanujan Math. Soc. Lecture Notes Series}, year={2007}, number={3}, pages={179--185} }