@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}
}