@inproceedings{Alhazov.etal:DRevSeq:PostUC2010, author = {Artiom Alhazov and Rudolf Freund and Kenichi Morita}, title = {Reversibility and Determinism in Sequential Multiset Rewriting}, booktitle = {Unconventional Computation: 9th International Conference, UC 2010, Tokyo, Japan, June 21-25, 2010. Proceedings}, editor = {Cristian S. Calude and Masami Hagiya and Kenichi Morita and Grzegorz Rozenberg and Jon Timmis}, series = {Lecture Notes in Computer Science}, volume = {6079}, publisher = {Springer}, year = {2010}, pages = {21--31}, bibdate = {07/12/10}, abstract = {We study reversibility and determinism aspects of sequential multiset processing systems, and the strong versions of these properties. Syntactic criteria are established for both strong determinism and for strong reversibility. It also shown that without control all four classes - deterministic, strongly deterministic, reversible, strongly reversible - are not universal, while allowing priorities or inhibitors the first and the third class become universal. Moreover, strongly deterministic multiset rewriting systems with priorities are also universal.}, url = {http://www.springerlink.com/content/dh2r3jhm04v14m80/}, } @inproceedings{Alhazov.etal:LOP:LASymposium2010, author = {Artiom Alhazov and Constantin Ciubotaru and {\relax Yu}rii Rogozhin and Sergiu Ivanov}, title = {The Membrane Systems Language Class}, booktitle = {2009 LA Winter Symposium}, address = {Kyoto, Japan}, year = {2010}, pages = {12-1--12-9}, bibdate = {07/12/10}, abstract = {The aim of this paper is to introduce the class of languages generated by the transitional model of membrane systems without cooperation and without additional ingredients. The fundamental nature of these basic systems makes it possible to also define the corresponding class of languages it in terms of derivation trees of context-free grammars. We also compare this class to the well-known language classes and discuss its properties.}, url = {http://www.nishizeki.ecei.tohoku.ac.jp/LA2009/program_winter.html}, } @inbook{Freund.Alhazov.Rogozhin.Verlan:SAChapter:HandbookMC, author = {Rudolf Freund and Artiom Alhazov and {\relax Yu}rii Rogozhin and Sergey Verlan}, title = {Communication {P}~Systems}, year = {2010}, publisher = {Oxford University Press}, pages = {118--143}, booktitle = {The Oxford Handbook of Membrane Computing}, editor = {{\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, url = {http://www.oup.com/us/catalog/general/subject/Mathematics/AppliedMathematics/?view=usa&sf=toc&ci=9780199556670}, } @inproceedings{Alhazov.Morita:DRevP:PostWMC10:2010, author = {Artiom Alhazov and Kenichi Morita}, title = {On Reversibility and Determinism in {P}~Systems}, booktitle = {Membrane Computing, 10th International Workshop, WMC 2009, Curtea de Arge{\c s}, Romania, August 24-27, 2009. Revised Selected and Invited Papers}, editor = {{\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {5957}, publisher = {Springer}, year = {2010}, pages = {158--168}, bibdate = {07/12/10}, abstract = {Membrane computing is a formal framework of distributed parallel computing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for reversible P systems with either priorities or inhibitors, and a negative conjecture is stated for reversible P systems without such control. Strongly reversible P systems without control have shown to only generate sub-finite sets of numbers; this limitation does not hold if inhibitors are used. Another concept considered is strong determinism, which is a syntactic property, as opposed to the determinism typically considered in membrane computing. Strongly deterministic P systems without control only accept sub-regular sets of numbers, while systems with promoters and inhibitors are universal.}, url = {http://dx.doi.org/10.1007/978-3-642-11467-0_12}, } @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/}, } @inproceedings{Alhazov.etal:InsDelNote:PreWMC10:2009, author = {Artiom Alhazov and Alexander Krassovitskiy and {\relax Yu}rii Rogozhin and Sergey Verlan}, title = {A Note on P Systems with Small-Size Insertion and Deletion}, booktitle = {Preproceedings of the Tenth Workshop on Membrane Computing}, pages = {534--537}, year = {2009}, editor = {{\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'i}n Riscos-N{\'u}{\~n}ez}, address = {Curtea de Arge{\c s}, Romania}, bibdate = {04/06/09}, abstract = {We present an overview of recent results on small size insertion-deletion P systems. Together with the ordinary definition we consider systems with priority of deletion over insertion. In both cases, obtained P systems are strictly more powerful than ordinary insertion-deletion systems, and in most of the cases they are computationally complete.We list several such results. When using the priority relation, the computational completeness may be achieved by context-free insertion and deletion of one symbol only.}, url = {http://www.gcn.us.es/?q=node/442}, } @inproceedings{Alhazov.Morita:DRevP:PreWMC10:2009, author = {Artiom Alhazov and Kenichi Morita}, title = {On Reversibility and Determinism in {P}~Systems}, booktitle = {Preproceedings of the Tenth Workshop on Membrane Computing}, pages = {129--140}, year = {2009}, editor = {{\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'i}n Riscos-N{\'u}{\~n}ez}, address = {Curtea de Arge{\c s}, Romania}, bibdate = {04/06/09}, abstract = {Membrane computing is a formal framework of distributed parallel computing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for one class and a negative conjecture is stated for a more restricted class of reversible P systems. For one class of strongly reversible P systems, a very strong limitation is shown, and it is shown that this limitation does not hold for a less restricted class. Another concept considered is strong determinism, which is a syntactic property, as opposed to the determinism typically considered in membrane computing. A limitation is shown of one class, while a less restricted class is universal.}, url = {http://www.gcn.us.es/?q=node/442}, } @inproceedings{Alhazov.etal:InflectionsRepl:PreWMC10:2009, 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}, booktitle = {Preproceedings of the Tenth Workshop on Membrane Computing}, pages = {116--128}, year = {2009}, editor = {{\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez and Agust{\'i}n Riscos-N{\'u}{\~n}ez}, address = {Curtea de Arge{\c s}, Romania}, bibdate = {04/06/09}, 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.gcn.us.es/?q=node/442}, } @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}, } @inproceedings{Alhazov.Morita:RevP:BWMC2009, author = {Artiom Alhazov and Kenichi Morita}, title = {A Short Note on Reversibility in {P}~Systems}, booktitle = {Seventh Brainstorming Week on Membrane Computing}, address = {Sevilla, Spain}, editor = {Rosa Guti{\'e}rrez-Escudero and Miguel-Angel Guti{\'e}rrez-Naranjo and {\relax Gh}eorghe P{\u a}un and Ignacio P{\'e}rez-Hurtado and Agust{\'\i}n Riscos-N{\'u}{\~n}ez}, volume = {1}, year = {2009}, month = {February 2-6}, pages = {23--28}, bibdate = {07/12/10}, abstract = {Membrane computing is a formal framework of distributed parallel computing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for one class and a negative conjecture is stated for a more restricted class of reversible P systems. For one class of strongly reversible P systems, a very strong limitation is found, and it is shown that this limitation does not hold for a less restricted class.}, url = {http://www.gcn.us.es/?q=node/414}, } @inproceedings{Alhazov.etal:mInsDel:BWMC2009, author = {Artiom Alhazov and Alexander Krassovitskiy and {Yu}rii Rogozhin and Sergey Verlan}, title = {P Systems with Minimal Insertion and Deletion}, booktitle = {Seventh Brainstorming Week on Membrane Computing}, address = {Sevilla, Spain}, editor = {Rosa Guti{\'e}rrez-Escudero and Miguel-Angel Guti{\'e}rrez-Naranjo and {\relax Gh}eorghe P{\u a}un and Ignacio P{\'e}rez-Hurtado and Agust{\'\i}n Riscos-N{\'u}{\~n}ez}, volume = {1}, year = {2009}, month = {February 2-6}, pages = {9--21}, bibdate = {07/12/10}, abstract = {In this paper we consider insertion-deletion P systems with priority of deletion over the insertion.We show that such systems with one symbol context-free insertion and deletion rules are able to generate PsRE. If one-symbol one-sided context is added to insertion or deletion rules but no priority is considered, then all recursively enumerable languages can be generated. The same result holds if a deletion of two symbols is permitted. We also show that the priority relation is very important and in its absence the corresponding class of P systems is strictly included in MAT.}, url = {http://www.gcn.us.es/?q=node/414}, } @inproceedings{Alhazov.etal:PDict:BWMC2009, 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}, booktitle = {Seventh Brainstorming Week on Membrane Computing}, address = {Sevilla, Spain}, editor = {Rosa Guti{\'e}rrez-Escudero and Miguel-Angel Guti{\'e}rrez-Naranjo and {\relax Gh}eorghe P{\u a}un and Ignacio P{\'e}rez-Hurtado and Agust{\'\i}n Riscos-N{\'u}{\~n}ez}, volume = {1}, year = {2009}, month = {February 2-6}, pages = {1--8}, bibdate = {07/12/10}, abstract = {Membrane computing is a formal framework of distributed parallel computing. In this paper we implement working with the prefix tree by P systems with strings and active membranes.}, url = {http://www.gcn.us.es/?q=node/414}, } @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}, } @inproceedings{Alhazov.etal:SharpP:PreWMC9:2008, author = {Artiom Alhazov and Liudmila Burtseva and Svetlana Cojocaru and {\relax Yu}rii Rogozhin}, title = {Computing Solutions of {\#}{P}-complete Problems by {P} Systems with Active Membranes}, booktitle = {Preproceedings of the Ninth Workshop on Membrane Computing}, pages = {59--70}, year = {2008}, editor = {Pierluigi Frisco and David Wolfe Corne and {\relax Gh}eorghe P\u{a}un}, address = {Edinburgh, UK}, bibdate = {04/06/09}, abstract = {Membrane computing is a formal framework of distributed parallel multiset processing. Due to massive parallelism and exponential space some intractable computational problems can be solved by P systems with active membranes in polynomial number of steps. In this paper we generalize this approach from decisional problems to the computational ones, by providing a solution of a #P-Complete problem, namely to compute the permanent of a binary matrix.}, url = {http://ppage.psystems.eu/uploads/0/0f/PreProcWMC9.pdf}, } @inproceedings{Alhazov.etal:PSync:PreWMC9:2008, author = {Artiom Alhazov and Maurice Margenstern and Sergey Verlan}, title = {Fast Synchronization in {P}~Systems}, booktitle = {Preproceedings of the Ninth Workshop on Membrane Computing}, pages = {71--84}, year = {2008}, editor = {Pierluigi Frisco and David Wolfe Corne and {\relax Gh}eorghe P\u{a}un}, address = {Edinburgh, UK}, bibdate = {04/06/09}, abstract = {We consider the problem of synchronizing the activity of all membranes of a P system. After pointing at the connection with a similar problem dealt with in the field of cellular automata where the problem is called the firing squad synchronization problem, FSSP for short, we provide two algorithms to solve this problem. One algorithm is non-deterministic and works in 2h+3, the other is deterministic and works in 3h+3, where h is the height of the tree describing the membrane structure.}, url = {http://ppage.psystems.eu/uploads/0/0f/PreProcWMC9.pdf}, } @inproceedings{Alhazov.Rogozhin:OutskinMinSA2m:PostWMC8:2007, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin}, title = {Skin Output in {P} Systems with Minimal Symport/Antiport and Two Membranes}, booktitle = {Membrane Computing, 8th International Workshop, WMC 2007, Thessaloniki, Greece, June 25-28, 2007 Revised Selected and Invited Papers}, editor = {George Eleftherakis and Petros Kefalas and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {4860}, publisher = {Springer}, year = {2007}, pages = {97--112}, bibdate = {07/12/10}, abstract = {It is known that symport/antiport P systems with two membranes and minimal cooperation can generate any recursively enumerable sets of natural numbers using exactly one superfluous object in the output membrane, where the output membrane is an elementary membrane. In this paper we consider symport/antiport P systems where the output membrane is the skin membrane. In this case we prove an unexpected characterization: symport/antiport P systems (and purely symport P systems) with two membranes and minimal cooperation generate exactly the recursively enumerable sets of natural numbers.}, url = {http://dx.doi.org/10.1007/978-3-540-77312-2_6}, } @inproceedings{Alhazov.Perez:UniformQSAT:PostMCU2007, author = {Artiom Alhazov and Mario de Jes{\'u}s P{\'e}rez-Jim{\'e}nez}, title = {Uniform Solution of {QSAT} Using Polarizationless Active Membranes}, booktitle = {Machines, Computations, and Universality, 5th International Conference, MCU 2007, Orl{\'e}ans, France, September 10-13, 2007, Proceedings}, editor = {J{\'e}r{\^o}me Olivier Durand-Lose and Maurice Margenstern}, series = {Lecture Notes in Computer Science}, volume = {4664}, publisher = {Springer}, year = {2007}, pages = {122--133}, bibdate = {07/12/10}, abstract = {It is known that the satisfiability problem (SAT) can be solved with a semi-uniform family of deterministic polarizationless P systems with active membranes with non-elementary membrane division. We present a double improvement of this result by showing that the satisfiability of a quantified Boolean formula (QSAT) can be solved by a uniform family of P systems of the same kind.}, url = {http://dx.doi.org/10.1007/978-3-540-74593-8_11}, } @inproceedings{Alhazov.etal:PartialContexts:PostMCU2007, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald and Sergey Verlan}, title = {Partial Halting in {P} Systems Using Membrane Rules with Permitting Contexts}, booktitle = {Machines, Computations, and Universality, 5th International Conference, MCU 2007, Orl{\'e}ans, France, September 10-13, 2007, Proceedings}, editor = {J{\'e}r{\^o}me Olivier Durand-Lose and Maurice Margenstern}, series = {Lecture Notes in Computer Science}, volume = {4664}, publisher = {Springer}, year = {2007}, pages = {110--121}, 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 derivation modes.}, keywords = {computational completeness, halting, minimal parallelism, P systems, permitting context}, url = {http://dx.doi.org/10.1007/978-3-540-74593-8_10}, } @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}, } @inproceedings{Alhazov.Rogozhin:MinSA2mToChar:PostWMC7:2006, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin}, title = {Towards a Characterization of {P} Systems with Minimal Symport/Antiport and Two Membranes}, booktitle = {Membrane Computing, 7th International Workshop, WMC 2006, Leiden, The Netherlands, July 17-21, 2006, Revised, Selected, and Invited Papers}, editor = {Hendrik-Jan Hoogeboom and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {4361}, publisher = {Springer}, year = {2006}, pages = {135--153}, bibdate = {07/12/10}, abstract = {We prove that any set of numbers containing zero generated by symport/antiport P systems with two membranes and minimal cooperation is finite (for both symport/antiport P systems and for purely symport P systems). On the other hand, one additional object in the output membrane allows symport/antiport P systems (purely symport P systems) with two membranes and minimal cooperation generate any recursively enumerable sets of natural numbers without zero. Thus we improve our previous results for symport/antiport P systems with two membranes and minimal cooperation from three ``garbage'' objects down to one object and for purely symport P systems from six objects down to one object. Thus we show the optimality of these results.}, url = {http://dx.doi.org/10.1007/11963516_9}, } @inproceedings{Alhazov.etal:Extended_Spiking:PostWMC7:2006, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald and Marija Slavkovik}, title = {Extended Spiking Neural {P}~Systems}, booktitle = {Membrane Computing, 7th International Workshop, WMC 2006, Leiden, The Netherlands, July 17-21, 2006, Revised, Selected, and Invited Papers}, editor = {Hendrik-Jan Hoogeboom and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {4361}, publisher = {Springer}, year = {2006}, pages = {123--134}, bibdate = {07/12/10}, abstract = {We consider extended variants of spiking neural P systems and show how these extensions of the original model allow for easy proofs of the computational completeness of extended spiking neural P systems and for the characterization of semilinear sets and regular languages by finite extended spiking neural P systems (defined by having only finite checking sets in the rules assigned to the cells) with only a bounded number of neurons.}, url = {http://dx.doi.org/10.1007/11963516_8}, } @inproceedings{Alhazov.etal:SASurvey:PostWMC6:2006, author = {Artiom Alhazov and Rudolf Freund and {\relax Yu}rii Rogozhin}, title = {Computational Power of Symport/Antiport: History, Advances and Open Problems}, booktitle = {Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers}, editor = {Rudolf Freund and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {3850}, publisher = {Springer}, year = {2006}, pages = {1--30}, bibdate = {07/12/10}, abstract = {We first give a historical overview of the most important results obtained in the area of P systems and tissue P systems with symport/antiport rules, especially with respect to the development of computational completeness results improving descriptional complexity parameters. We consider the number of membranes (cells in tissue P systems), the weight of the rules, and the number of objects. Then we establish our newest results: P systems with only one membrane, symport rules of weight three, and with only seven additional objects remaining in the skin membrane at the end of a halting computation are computationally complete; P systems with minimal cooperation, i.e., P systems with symport/antiport rules of size one and P systems with symport rules of weight two, are computationally complete with only two membranes with only three and six, respectively, superfluous objects remaining in the output membrane at the end of a halting computation.}, url = {http://dx.doi.org/10.1007/11603047_1}, } @inproceedings{Alhazov.etal:PCarpet:PostWMC6:2006, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald}, title = {Symbol/Membrane Complexity of {P} Systems with Symport/Antiport Rules}, booktitle = {Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers}, editor = {Rudolf Freund and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {3850}, publisher = {Springer}, year = {2006}, pages = {96--113}, bibdate = {07/12/10}, abstract = {We consider P systems with symport/antiport rules and small numbers of symbols and membranes and present several results for P systems with symport/antiport rules simulating register machines with the number of registers depending on the number s of symbols and the number m of membranes. For instance, any recursively enumerable set of natural numbers can be generated (accepted) by systems with s> = 2 symbols and m>=1 membranes such that m+s>=6. In particular the result of the original paper [16] proving universality for three symbols and four membranes is improved (e.g., three symbols and three membranes are sufficient). The general results that P systems with symport/antiport rules with s symbols and m membranes are able to simulate register machines with max{m(s-2),(m-1)(s-1)} registers also allows us to give upper bounds for the numbers s and m needed to generate/accept any recursively enumerable set of k- dimensional vectors of non-negative integers or to compute any partial recursive function f:N^a->N^b. Finally, we also study the computational power of P systems with symport/antiport rules and only one symbol: with one membrane, we can exactly generate the family of finite sets of non-negative integers; with one symbol and two membranes, we can generate at least all semilinear sets. The most interesting open question is whether P systems with symport/antiport rules and only one symbol can gain computational completeness (even with an arbitrary number of membranes) as it was shown for tissue P systems in [1].}, url = {http://dx.doi.org/10.1007/11603047_7}, } @inproceedings{Alhazov:ProtonBicat:PostWMC6:2006, author = {Artiom Alhazov}, title = {Number of Proton/Bi-stable Catalysts and Membrane in {P} Systems. {T}ime Freeness}, booktitle = {Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers}, editor = {Rudolf Freund and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {3850}, publisher = {Springer}, year = {2006}, pages = {79--95}, bibdate = {07/12/10}, abstract = {Proton pumping P systems are a variant of membrane systems with both rewriting rules and symport/antiport rules, where a set of objects called protons is distinguished, every cooperative symport or antiport rule involves a proton, but no rewriting rule does. Time-freeness property means the result of all computations does not depend on the time it takes to execute the rules. The goal of this article is to improve (showing that two membranes are sufficient) the known universality results on proton pumping P systems, establishing at the same time an upper bound on the number of protons, namely one, or four for time-free systems. All results mentioned hold for proton pumping P systems with non-cooperative rewriting and either symport/antiport rules of weight one (classical variant) or symport rules of weight at most two. As a corollary, we obtain the universality of P systems with one membrane and one bi-stable catalyst, or the universality of time-free P systems with one membrane and four bi-stable catalysts. All universality results are stated as generating RE (except the time-free systems without targets generate PsRE).}, url = {http://dx.doi.org/10.1007/11603047_6}, } @inproceedings{Alhazov.etal:PolarCreaOC:PostSYNASC:IEEE2005, author = {Artiom Alhazov and Rudolf Freund and Agust{\'i}n Riscos-N{\'u}{\~n}ez}, title = {One and Two Polarizations, Membrane Creation and Objects Complexity in {P} Systems}, booktitle = {Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 05}, publisher = {IEEE Computer Society}, year = {2005}, pages = {385--394}, bibdate = {07/12/10}, 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 here show that they generate all recursively enumerable languages, and 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. Then we prove that 10+m symbols are enough 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, only using rules of rewriting and sending objects out. We show that accepting can be done by deterministic systems. Finally, remarks and open questions are presented.}, url = {http://doi.ieeecomputersociety.org/10.1109/SYNASC.2005.54}, } @inproceedings{Alhazov.etal:tCarpet:PostDLT2005, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald}, title = {Tissue {P} Systems with Antiport Rules and Small Numbers of Symbols and Cells}, booktitle = {Developments in Language Theory, 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005, Proceedings}, editor = {Clelia de Felice and Antonio Restivo}, series = {Lecture Notes in Computer Science}, volume = {3572}, publisher = {Springer}, year = {2005}, pages = {100--111}, bibdate = {07/12/10}, abstract = {We consider tissue P systems with antiport rules and investigate their computational power when using only a (very) small number of symbols and cells. Even when using only one symbol, any recursively enumerable set of natural numbers can be generated with at most seven cells. 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 at most 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, e.g., 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.}, keywords = {antiport rules, cells, membrane computing, tissue P systems}, url = {http://www.springerlink.com/content/h4w6864wgf2qhyq6/}, } @inproceedings{Alhazov.etal:Pol2Compl:PostMCU2004:2005, author = {Artiom Alhazov and Rudolf Freund and {\relax Gh}eorghe P{\u a}un}, title = {Computational Completeness of {P} Systems with Active Membranes and Two Polarizations}, booktitle = { Machines, Computations, and Universality: 4th International Conference, MCU2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers}, editor = {Maurice Margenstern}, series = {Lecture Notes in Computer Science}, volume = {3354}, publisher = {Springer}, year = {2005}, pages = {178--189}, bibdate = {07/12/10}, abstract = {P systems with active membranes using only two electrical charges and only rules of type (a), i.e., evolution rules used in parallel in the regions of the membrane system, and of type (c), i.e., communication rules sending out an object of a membrane thereby possibly changing the polarization of this membrane, assigned to at most two membranes are shown to be computationally complete, which improves the previous result of this type with respect to the number of polarizations as well as to the number of membranes. Allowing a special variant (c_\lambda) of rules of type (c) to delete symbols by sending them out, even only one membrane is enough.}, url = {http://www.springerlink.com/content/7mllx684jbabqtk2/}, } @inproceedings{Alhazov.Sburlan:PMRncooProInh:PostWMC5:2005, author = {Artiom Alhazov and Drago{\c s} Sburlan}, title = {Ultimately Confluent Rewriting Systems. {P}arallel Multiset-Rewriting with Permitting or Forbidding Contexts}, booktitle = {International Workshop WMC5, Milano, Italy, 2004}, editor = {Giancarlo Mauri and {\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {3365}, publisher = {Springer}, year = {2005}, pages = {178--189}, bibdate = {07/12/10}, abstract = {The aim of this paper is to study the power of parallel multiset-rewriting systems with permitting or forbidding context (or P systems with non-cooperative rules with promoters or inhibitors). The main results obtained are those if we use promoters or inhibitors of weight two, then the systems are computational universal. Moreover, both constructions satisfy a special property we define: they are ultimately confluent. This means that if the system allows at least one halting computation, then their final configurations are reachable from any reachable configuration. The other property both constructions satisfy is that a system allowing at least one halting computation will halt with probability 1.}, url = {http://www.springerlink.com/content/844258u0uu3vrept/}, } @inproceedings{Alhazov.Freund:Pol2Eff:PostWMC5:2005, author = {Artiom Alhazov and Rudolf Freund}, title = {On the Efficiency of {P} Systems with Active Membranes and Two Polarizations}, booktitle = {International Workshop WMC5, Milano, Italy, 2004}, editor = {Giancarlo Mauri and {\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {3365}, publisher = {Springer}, year = {2005}, pages = {146--160}, bibdate = {07/12/10}, abstract = {We present an algorithm for deterministically deciding SAT in linear time by P systems with active membranes using only two polarizations and rules of types (a), (c) and (e). Moreover, various restrictions on the general form of the rules are considered: global, non-renaming, independent of the polarization, preserving it, changing it, producing two membranes with different polarizations, having exactly one or two objects in (each membrane of) the right-hand side, improving results from [1]. Several problems related to different combinations of these restrictions are formulated, too.}, url = {http://www.springerlink.com/content/2be8vy2yfy8u8gka/}, } @inproceedings{Alhazov.Sburlan:PMRncooPro:BWMC2004, author = {Artiom Alhazov and Drago{\c s} Sburlan}, title = {({U}ltimately Confluent) Parallel Multiset-Rewriting Systems with Context}, booktitle = {Second Brainstorming Week on Membrane Computing Sevilla, Spain, February 2-7 2004}, year = {2004}, month = {February 2-7}, address = {Sevilla, Spain}, editor = {{\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, pages = {45--52}, bibdate = {07/12/10}, abstract = {The aim of this paper is to study the power of parallel multiset-rewriting systems with permitting context (or P systems with non-cooperative rules with promoters). The main result obtained is that if we use promoters of weight two, then the system is universal. Moreover, the construction satisfies a special property we define: it is ultimately confluent. This means that if the system allows at least one halting computation, then its final configuration is reachable from any reachable configuration.}, url = {http://www.gcn.us.es/2BWMC/Volumen.htm}, } @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}, } @inbook{Alhazov.etal:Graph:AspectsMC2004, author = {Artiom Alhazov and Carlos Mart{\'i}n-Vide and Linqiang Pan}, title = {Solving Graph Problems by {P} Systems with Restricted Elementary Active Membranes}, series = {Lecture Notes in Computer Science}, volume = {2950}, year = {2004}, publisher = {Springer}, pages = {1--22}, booktitle = {Aspects of Molecular Computing - Essays dedicated to Tom Head on the occasion of his 70th birthday}, editor = {Nata{\u s}a Jonoska and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg}, bibdate = {01/22/10}, abstract = {P systems are parallel molecular computing models based on processing multisets of objects in cell-like membrane structures. In this paper we give membrane algorithms to solve the vertex cover problem and the clique problem in linear time with respect to the number of vertices and edges of the graph by recognizing P systems with active membranes using 2-division. Also, the linear time solution of the vertex cover problem is given using P systems with active membranes using 2-division and linear resources.}, url = {http://www.springerlink.com/content/e9c2pk249m1tdj7b/}, } @techreport{Alhazov.Verlan:TinySA:2008, author = {Artiom Alhazov and Sergey Verlan}, title = {Minimization Strategies for Maximally Parallel Multiset Rewriting Systems}, institution = {Turku Centre for Computer Science}, type = {Technical Report}, number = {862}, year = {2008}, bibdate = {03/03/08}, abstract = {Maximally parallel multiset rewriting systems (MPMRS) present a convenient way to express relations between unstructured objects. The functioning of various computational devices may be expressed in terms of MPMRS (e.g. register machines and many variants of P systems). In particular, this means that MPMRS are computationally complete; however, a direct translation leads to quite a big number of rules. Like for other classes of computationally complete devices there is a challenge to find a universal system having the smallest number of rules. In this article we present different rule minimization strategies for MPMRS based on encodings and structural transformations. We apply these strategies to the translation of a small universal register machine (Korec, 1996) and we show that there exists a universal MPMRS with 23 rules. Since MPMRS are identical to a restricted variant of P systems with antiport rules, the results we obtained improve previously known results on the number of rules for that systems.}, url = {http://tucs.fi/publications/insight.php?id=tAlVe08a}, } @inproceedings{Alhazov.etal:PSync:PostWMC9:2009, author = {Artiom Alhazov and Maurice Margenstern and Sergey Verlan}, title = {Fast Synchronization in {P}~Systems}, booktitle = {Membrane Computing: 9th International Workshop}, pages = {118--128}, year = {2009}, editor = {David Wolfe Corne and Pierluigi Frisco and {\relax Gh}eorghe P\u{a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {5391}, publisher = {Springer}, venue = {Edinburgh, UK}, bibdate = {04/06/09}, abstract = {We consider the problem of synchronizing the activity of all membranes of a P system. After pointing the connection with a similar problem dealt with in the field of cellular automata, where the problem is called the firing squad synchronization problem, FSSP for short, we provide two algorithms to solve this problem for P systems. One algorithm is non-deterministic and works in 2h+3 steps, the other is deterministic and works in 3h+3 steps, where h is the height of the tree describing the membrane structure.}, url = {http://dx.doi.org/10.1007/978-3-540-95885-7_9}, } @inproceedings{Alhazov.etal:SharpP:PostWMC9:2009, author = {Artiom Alhazov and Liudmila Burtseva and Svetlana Cojocaru and {\relax Yu}rii Rogozhin}, title = {Solving {PP}-Complete and {\#}{P}-Complete Problems by {P}~Systems with Active Membranes}, booktitle = {Membrane Computing: 9th International Workshop}, pages = {108--117}, year = {2009}, editor = {David Wolfe Corne and Pierluigi Frisco and {\relax Gh}eorghe P\u{a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {5391}, publisher = {Springer}, venue = {Edinburgh, UK}, bibdate = {04/06/09}, abstract = {Membrane computing is a formal framework of distributed parallel multiset processing. Due to massive parallelism and exponential space some intractable computational problems can be solved by P systems with active membranes in a polynomial number of steps. In this paper we generalize this approach from decisional problems to the computational ones, by providing a solution of a #P-complete problem, namely to compute the permanent of a binary matrix. The implication of this result to the PP complexity class is discussed and compared to known results about NP U co-NP.}, url = {http://dx.doi.org/10.1007/978-3-540-95885-7_8}, } @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{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/}, } @phdthesis{Alhazov:PhD:2006, author = {Artiom Alhazov}, title = {Communication in Membrane Systems with Symbol Objects}, school = {University of Sevilla, Spain}, year = {2006}, address = {Sevilla, Spain}, abstract = {This thesis deals with membrane systems with symbol objects as a theoretical framework of distributed parallel multiset processing systems. A halting computation can accept, generate or process a number, a vector or a word, so the system globally defines (by the results of all its computations) a set of numbers or a set of vectors or a set of words, (i.e., a language) or a function. The ability of these systems to solve particular problems is investigated, as well as their computational power, e.g., the language families defined by different classes of these systems are compared to the classical ones, i.e., regular, context-free, languages generated by extended tabled 0L systems, languages generated by matrix grammars without appearance checking, recursively enumerable languages, etc. Special attention is paid to communication of objects between the regions and to the ways of cooperation between the objects. An attempt to formalize the membrane systems is made, and a software tool is constructed for the non-distributed cooperative variant, the configuration browser, i.e., a simulator, where the user chooses the next configuration among the possible ones and can go back. Different distributed models are considered. In the evolution--communication model rewriting-like rules are separated from transport rules. Proton pumping systems are a variant of the evolution--communication systems with a restricted way of cooperation. A special membrane computing model is a purely communicative one: the objects are moved together through a membrane. Determinism is a special property of computational systems; the question of whether this restriction reduces the computational power is addressed. The results on proton pumping systems can be carried over to the systems with bistable catalysts. Some particular examples of membrane systems applications are solving NP-complete problems in polynomial time, and solving the sorting problem.}, keywords = {P systems, membrane computing, symport, antiport, parallel multiset processing}, eprint = {http://psystems.disco.unimib.it/download/Alhazovthesis.zip}, url = {http://www.tesisenxarxa.net/TDX-0704107-093050/}, } @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}, } @inproceedings{Alhazov.etal:MinCoo3m:PostWMC5:2005, author = {Artiom Alhazov and Maurice Margenstern and Vladimir Rogozhin and {\relax Yu}rii Rogozhin and Sergey Verlan}, title = {Communicative {P} Systems with Minimal Cooperation}, booktitle = {International Workshop WMC5, Milano, Italy, 2004}, editor = {Giancarlo Mauri and {\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {3365}, publisher = {Springer}, year = {2005}, pages = {146--160}, abstract = {We prove that two classes of communicative P systems with 3 membranes and with minimal cooperation, namely P systems with symport/antiport rules of size 1 and and P systems with symport rules of size 2, are computationally complete: they generate all recursively enumerable sets of vectors of nonnegative integers. The result of computation is obtained in the elementary membrane.}, url = {http://www.springerlink.com/content/66xpyl1a4vlg8fw7/}, } @inproceedings{Alhazov:MinECP:BWMC2003, author = {Artiom Alhazov}, title = {Minimizing Evolution-Communication {P} Systems and {EC} {P} Automata}, booktitle = {Brainstorming Week on Membrane Computing, Tarragona, February 5-11 2003}, year = {2003}, month = {February 5-11}, address = {Tarragona, Spain}, editor = {Matteo Cavaliere and Carlos Mart{\'i}n-Vide and {\relax Gh}eorghe P{\u a}un}, pages = {23--31}, abstract = {Evolution-communication P systems is a variant of P systems allowing both rewriting rules and symport/antiport rules. The idea is to separate rewriting and communication and this separation helps to obtain good generative capacity even restricting both evolution and communicative rules. The purpose of this paper is to solve an open problem stated in [1] namely generating PsRE instead of NRE. 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. Here EC P automata are also introduced and it is proved that 2-membrane EC P automata with a promoter can accept RE.}, eprint = {http://psystems.disco.unimib.it/download/rep26.zip}, url = {http://grlmc-dfilrom.urv.cat/grlmc/reports/rep26.html}, } @inproceedings{Alhazov:GenClasses:BWMC2003, author = {Artiom Alhazov}, title = {Generating Classes of Languages by {P} Systems and Other Devices}, booktitle = {Brainstorming Week on Membrane Computing, Tarragona, February 5-11 2003}, year = {2003}, month = {February 5-11}, address = {Tarragona}, editor = {Matteo Cavaliere and Carlos Mart{\'i}n-Vide and {\relax Gh}eorghe P{\u a}un}, pages = {18--22}, abstract = {The purpose of this paper is to give a finite description of the classes of languages (as opposed to the description of languages) by a generative device, like a P system. The definition of the generated class is inspired by the forbidding-enforcing systems. A more general definition of generating a class of languages by two devices is also given and some relationships between these two definitions are studied.}, eprint = {http://psystems.disco.unimib.it/download/rep26.zip}, url = {http://grlmc-dfilrom.urv.cat/grlmc/reports/rep26.html}, } @inproceedings{Alhazov.Sburlan:PSort:PreWMC2003, author = {Artiom Alhazov and Drago{\c s} Sburlan}, title = {Static Sorting Algorithms for {P}~Systems}, booktitle = {Preproceedings of the Workshop on Membrane Computing}, year = {2003}, month = {July 17-22}, address = {Tarragona}, editor = {Artiom Alhazov and Carlos Mart{\'i}n-Vide and {\relax Gh}eorghe P{\u a}un}, pages = {17--40}, abstract = {We explore here P Sorting. Traditional studies of sorting assume a constant time for comparing two numbers and compute the time complexity with respect to the number of components of a vector to be sorted. In this paper we assume the number of components to be a fixed number k, and study various algorithms with distinct generative features based on different models of P systems, and their time complexity with respect to the maximal number or to their sum. Massive parallel computations that can be realized within the framework of P systems offer a premise to major improvements of the classical integer sorting problems. Despite this important characteristic we will see that, depending on the model used, the massive parallelism feature cannot be always used, and so, some results will have the complexity ``comparable'' with the classical integer sorting algorithms. Still, computing an (ordered) word from an (unordered) multiset can be a goal not only for computer science but also, at least, for bio-synthesis (separating mixed objects according to some characteristics). Here, we will pass from ranking algorithms that, starting with numbers represented as multisets produce symbols in an order, to effective sorting algorithms.}, eprint = {http://psystems.disco.unimib.it/download/WMC03.zip}, url = {http://grlmc-dfilrom.urv.cat/grlmc/reports/WMC03.html}, } @inproceedings{Alhazov.Cavaliere:Proton:PostWMC2003:2004, author = {Artiom Alhazov and Matteo Cavaliere}, title = {Proton Pumping {P}~Systems}, booktitle = {Membrane Computing, International Workshop, WMC 2003, Tarragona, Spain July, 17-22, 2003, Revised Papers}, year = {2004}, month = {July}, publisher = {Springer}, editor = {Carlos Mart{\'i}n-Vide and Giancarlo Mauri and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg and Arto Salomaa}, series = {Lecture Notes in Computer Science}, volume = {2933}, pages = {1--18}, abstract = {We propose here a (biologically inspired) model of P system called proton pumping P system that is a special case of evolution-communication P system. In cell biology there are transport mechanisms, involving protons. We generalize this idea by considering a few different types of protons. A proton pumping P system is, essentially, an evolution-communication P system where a special subset of symbol-objects (called protons) is used. In such a system we have simple evolution rules (classical evolution rules without target indications) symport and antiport rules that exchange some objects (among them, possibly other protons) for a proton; taking inspiration from biology, this particular type of antiports is often called proton pumping rules. We show that, as expected, the new model is universal, using non-cooperative rules, symport and antiport rules of weight one, and enough types of protons available for the computation. If we decrease the number of types of protons to one or two, then the model is at least as powerful as ET0L system, provided that (total) weak or strong priority of antiport rules over symport and evolution rules are used. Finally, we consider some descriptional complexity measures (again, inspired from biology) for the newly introduced model.}, url = {http://www.springerlink.com/content/w034nr0qjnd0yd6c/}, } @inproceedings{Alhazov.Cavaliere:PPump:PreWMC2003, author = {Artiom Alhazov and Matteo Cavaliere}, title = {Proton Pumping {P}~Systems}, booktitle = {Preproceedings of the Workshop on Membrane Computing}, year = {2003}, month = {July 17-22}, address = {Tarragona}, editor = {Artiom Alhazov and Carlos Mart{\'i}n-Vide and {\relax Gh}eorghe P{\u a}un}, pages = {1--16}, abstract = {We propose here a (biologically inspired) model of P system called proton pumping P system that is a special case of evolution--communication P system. In cell biology there are transport mechanisms, involving protons. We generalize this idea by considering a few different types of protons. A proton pumping P system is, essentially, an evolution--communication P system where a special subset of symbol-objects (called protons) is used. In such a system we have simple evolution rules (classical evolution rules without target indications), symport and antiport rules that exchange some objects (among them, possibly, other protons) for a proton; taking inspiration from biology this particular type of antiports is often called proton pumping rules. We show that, as expected, the new model is universal, using non-cooperative rules, symport and antiport rules of weight one, and enough types of protons available for the computation. If we decrease the number of types of protons to one or two, then the model is at least as powerful as PsET0L, provided that (total) weak or strong priority of antiport rules over symport and evolution rules are used. Finally, we consider some descriptional complexity measures (again, inspired from biology) for the newly introduced model.}, eprint = {http://psystems.disco.unimib.it/download/WMC03.zip}, url = {http://grlmc-dfilrom.urv.cat/grlmc/reports/WMC03.html}, } @inproceedings{Alhazov:DECP:BWMC2004, author = {Artiom Alhazov}, title = {On the Power of Deterministic {EC P Systems}}, booktitle = {Second Brainstorming Week on Membrane Computing Sevilla, Spain, February 2-7 2004}, year = {2004}, month = {February 2-7}, address = {Sevilla, Spain}, editor = {{\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, pages = {11--15}, 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 (recognizing) 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.}, url = {http://www.gcn.us.es/2BWMC/Volumen.htm}, } @inproceedings{Alhazov:Activators:BWMC2004, author = {Artiom Alhazov}, title = {A Note on {P} Systems with Activators}, booktitle = {Second Brainstorming Week on Membrane Computing Sevilla, Spain, February 2-7 2004}, year = {2004}, month = {February 2-7}, address = {Sevilla, Spain}, editor = {{\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, pages = {16--19}, abstract = {The usual assumption in P systems behavior is that of maximal parallelism, however in living cells it is not the case because they have a limited number of enzymes. The aim of this paper is to try to merge these ideas by introducing a notion of activator - a formal model of enzyme as a usual symbol-object, more or less a middle notion between a catalyst and a promoter. Each activator executes one (context-free) rule and can evolve in the same step. The rules will need activators to be applied, so the parallelism of each rule is maximal, but limited to the number of its activators. Such systems can generate any recursively enumerable language or deterministically accept any recursively enumerable set of vectors of nonnegative integers. It is open what is the power of P systems with uniport rules and activators.}, url = {http://www.gcn.us.es/2BWMC/Volumen.htm}, } @inproceedings{Alhazov.Sburlan:PMRncooPro:PreWMC5:2004, author = {Artiom Alhazov and Drago{\c s} Sburlan}, title = {({U}ltimately Confluent) Parallel Multiset-Rewriting Systems with Permitting Context}, editor = {Giancarlo Mauri and {\relax Gh}eorghe P{\u a}un and Claudio Zandron}, booktitle = {Pre-proceedings of the Fifth Workshop on Membrane Computing}, address = {Milano, Italy}, year = {2004}, month = {June}, pages = {95--103}, abstract = {The aim of this paper is to study the power of parallel multiset-rewriting systems with permitting contexts (or P systems with non-cooperative rules with promoters). The main result obtained is that if we use promoters of weight two, then the system is universal. Moreover, the construction satisfies a special property we define: it is ultimately confluent. This means that if the system allows at least one halting computation, then its final configuration is reachable from any reachable configuration.}, url = {http://psystems.disco.unimib.it/procwmc5.html}, } @inproceedings{Alhazov.Freund:Pol2Eff:PreWMC5:2004, author = {Artiom Alhazov and Rudolf Freund}, title = {On the Efficiency of {P} Systems with Active Membranes and Two Polarizations}, editor = {Giancarlo Mauri and {\relax Gh}eorghe P{\u a}un and Claudio Zandron}, booktitle = {Pre-proceedings of the Fifth Workshop on Membrane Computing}, address = {Milano, Italy}, year = {2004}, month = {June}, pages = {81--94}, abstract = {We present an algorithm for deterministically deciding SAT in linear time by P systems with active membranes using only two polarizations and rules of types (a), (c) and (e). Moreover, various restrictions on the general form of the rules are considered: global, non-renaming, independent of the polarization, preserving it, changing it, producing two membranes with different polarizations, having exactly one or two objects in (each membrane of) the right-hand side, improving results from [1]. Several problems related to different combinations of these restrictions are formulated, too.}, url = {http://psystems.disco.unimib.it/procwmc5.html}, } @inproceedings{Alhazov.etal:Pol2:BWMC2004, author = {Artiom Alhazov and Rudolf Freund and {\relax Gh}eorghe P{\u a}un}, title = {{P} systems with Active Membranes and Two Polarizations}, booktitle = {Second Brainstorming Week on Membrane Computing Sevilla, Spain, February 2-7 2004}, year = {2004}, month = {February 2-7}, address = {Sevilla, Spain}, editor = {{\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, pages = {20--36}, abstract = {P systems with active membranes using only two electrical charges and only rules of types (a) and (c) assigned to at most two membranes are shown to be computationally complete -- thus improving the previous result of this type from the point of view of the number of polarizations as well as with respect to the number of membranes. Allowing a special variant of rules of type (c) to delete symbols by sending them out, even only one membrane is needed. Moreover, we present an algorithm for deterministically deciding SAT in linear time using only two polarizations and global rules of types (a), (c), and (e).}, url = {http://www.gcn.us.es/2BWMC/Volumen.htm}, } @inproceedings{Alhazov.Ishdorj:MemOps:BWMC2004, author = {Artiom Alhazov and {\relax Ts}eren-Onolt Ishdorj}, title = {Membrane Operations in {P} systems with Active Membranes}, booktitle = {Second Brainstorming Week on Membrane Computing Sevilla, Spain, February 2-7 2004}, year = {2004}, month = {February 2-7}, address = {Sevilla, Spain}, editor = {{\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, pages = {37--44}, abstract = {In this paper we define a general class of P systems covering some biological operations with membranes, including evolution, communication modifying the membrane structure, and we describe and formally specify some of these operations: membrane merging, membrane separation, membrane release. We also investigate a particular combination of types of rules that can be used in solving SAT problem in linear time.}, url = {http://www.gcn.us.es/2BWMC/Volumen.htm}, } @inproceedings{Pan.Alhazov.Ishdorj:Further_MemOps:BWMC2004, author = {Linqiang Pan and Artiom Alhazov and {\relax Ts}eren-Onolt Ishdorj}, title = {Further Remarks on {P} systems with Active Membranes Separation, Merging and Release Rules}, booktitle = {Second Brainstorming Week on Membrane Computing Sevilla, Spain, February 2-7 2004}, year = {2004}, month = {February 2-7}, address = {Sevilla, Spain}, editor = {{\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Alvaro Romero-Jim{\'e}nez and Fernando Sancho-Caparrini}, pages = {316--324}, 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, Ts. Ishdorj. A universality result related to membrane separation is also obtained.}, url = {http://www.gcn.us.es/2BWMC/Volumen.htm}, } @inproceedings{Alhazov:ProtonBicat:PreWMC6:2005, author = {Artiom Alhazov}, title = {Number of Proton/Bi-stable Catalysts and Membrane in {P} Systems. {T}ime Freeness}, editor = {Rudolf Freund and Georg Lojka and Marion Oswald and {\relax Gh}eorghe P{\u a}un}, booktitle = {Pre-Proc. of the Sixth Workshop on Membrane Computing}, address = {Vienna, Austria}, year = {2005}, pages = {102--122}, abstract = {Proton pumping P systems are a variant of membrane systems with both rewriting rules and symport/antiport rules, where a set of objects called protons is distinguished, every cooperative symport or antiport rule involves a proton, but no rewriting rule does. Time-freeness property means the result of all computations does not depend on the rules execution times. This article's aim is to improve (showing that two membranes are sufficient) the known universality results on proton pumping P systems establishing at the same time an upper bound on the number of protons, namely one, or four for time-free systems. All results mentioned are valid for proton pumping P systems with non-cooperative rewriting and either symport/antiport rules of weight 1 (classical variant) or symport rules of weight at most 2. As a corollary we obtain the universality of P systems with one membrane and one bi-stable catalyst, or the universality of time-free P systems with one membrane and four bi-stable catalysts. All universality results are stated as generating RE (except the time-free systems without targets generate PsRE).}, url = {http://www.emcc.at/WMC6/WMC6PreProcFull.pdf}, } @inproceedings{Alhazov.etal:PolarCreaOC:PreTAPS2005, author = {Artiom Alhazov and Rudolf Freund and Agust{\'i}n Riscos-N{\'u}{\~n}ez}, title = {One and Two Polarizations, Membrane Creation and Objects Complexity in {P} Systems}, editor = {Gabriel Ciobanu and {\relax Gh}eorghe P{\u a}un}, booktitle = {Pre-Proc. of First International Workshop on Theory and Application of P Systems}, address = {Timi{\c s}oara, Romania}, year = {2005}, pages = {9--18}, 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 here show that they generate all recursively enumerable languages, and 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. Then we prove that 10+m symbols are enough to generate any recursively enumerable language over m symbols. P systems with active membranes and 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, and 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, only using rewriting-like rules and rules of sending objects out. We show that accepting can be done by even deterministic systems. Finally, a number of remarks and open questions is presented.}, url = {http://psystems.disco.unimib.it/download/volTAPS.pdf}, } @inproceedings{Alhazov.etal:PCarpet:PreWMC6:2005, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald}, title = {Symbol / Membrane Complexity of {P} Systems with Symport / Antiport Rules}, editor = {Rudolf Freund and Georg Lojka and Marion Oswald and {\relax Gh}eorghe P{\u a}un}, booktitle = {Pre-Proc. of the Sixth Workshop on Membrane Computing}, address = {Vienna, Austria}, year = {2005}, pages = {123--146}, abstract = {We consider P systems with symport / antiport rules and small numbers of symbols and membranes and present several results for P systems with symport / antiport rules simulating register machines with the number of registers depending on the number s of symbols and the number m of membranes. For instance, any recursively enumerable set of natural numbers can be generated (accepted) by systems with s> = 2 symbols and m>=1 membranes such that m+s>=6. In particular the result of the original paper [16] proving universality for three symbols and four membranes is improved (e.g., three symbols and three membranes are sufficient). The general results that P systems with symport / antiport rules with s symbols and m membranes are able to simulate register machines with max{m(s-2),(m-1)(s-1)} registers also allows us to give upper bounds for the numbers s and m needed to generate/accept any recursively enumerable set of k- dimensional vectors of non-negative integers or to compute any partial recursive function f:N^a->N^b. Finally, we also study the computational power of P systems with symport / antiport rules and only one symbol: with one membrane, we can exactly generate the family of finite sets of non-negative integers; with one symbol and two membranes, we can generate at least all semilinear sets. The most interesting open question is whether P systems with symport / antiport rules and only one symbol can gain computational completeness (even with an arbitrary number of membranes) as it was shown for tissue P systems in [1].}, url = {http://www.emcc.at/WMC6/WMC6PreProcFull.pdf}, } @inproceedings{Alhazov:MPMRSbrowser:BWMC2005, author = {Artiom Alhazov}, title = {Maximally Parallel Multiset-Rewriting Systems: Browsing the Configurations}, editor = {Miguel-Angel Guti{\'e}rrez-Naranjo and Agust{\'\i}n Riscos-N{\'u}{\~n}ez and Francisco-Jos{\'e} Romero-Campero and Drago{\c s} Sburlan}, booktitle = {Proceedings of the {T}hird {B}rainstorming {W}eek on {M}embrane {C}omputing}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {1--10}, abstract = {The aim of this research is to produce an algorithm for the software that would let a researcher to observe the evolution of maximally parallel multiset-rewriting systems with permitting and forbidding contexts, browsing the configuration space by following transitions like following hyperlinks in the World-Wide Web. The relationships of maximally parallel multiset-rewriting systems with other rewriting systems are investigated, such as Petri nets different kinds of P systems, Lindenmayer systems grammar systems, regulated grammars.}, url = {http://www.gcn.us.es/3BWMC/Volumen.htm}, } @inproceedings{Alhazov:SAT_SAdiv:ESF2005, author = {Artiom Alhazov}, title = {Solving {SAT} by Symport/Antiport {P} Systems with Membrane Division}, booktitle = {Proceedings of the {ESF} {E}xploratory {W}orkshop on {C}ellular {C}omputing ({C}omplexity {A}spects)}, editor = {Miguel-Angel Guti{\'e}rrez-Naranjo and {\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {1--6}, abstract = {We present an O(n)+O(log m)-time solution of SAT with n variables and m clauses by a uniform family of deterministic P systems with communication rules (antiport-2/1 and antiport-1/2) and membrane division rules (without polarization) and unstructured environment. Nothing is sent to the environment except yes or no, in one copy. We can even start with the empty environment if we also use symport-1 rules.}, eprint = {http://aartiom.50webs.com/articles/28fenix-1_ESF.pdf}, } @inproceedings{Alhazov.Cavaliere:ECTimeFree:BWMC2005, author = {Artiom Alhazov and Matteo Cavaliere}, title = {Evolution-Communication {P} Systems: Time-Freeness}, booktitle = {Proceedings of the {T}hird {B}rainstorming {W}eek on {M}embrane {C}omputing}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {11--18}, abstract = {Membrane computing is a (biologically motivated) theoretical framework of distributed parallel computing. If symbol-objects are considered then membrane systems (also called P systems) are distributed multiset processing systems. In evolution-communication (EC) P systems the computation is carried out with the use of non-cooperative rewriting rules and with (usually the minimally cooperative) transport rules. The goal of this article is to improve the existing results on evolution-communication P systems. It is known that EC P systems with 2 membranes are universal, and so are time-free EC P systems with targets with 3 membranes. We prove that any recursively enumerable set of vectors of nonnegative integers can be generated by time-free EC P systems (without targets) with 2 membranes thus improving both results.}, url = {http://www.gcn.us.es/3BWMC/Volumen.htm}, } @inproceedings{Alhazov.Freund:SA1m5s:BWMC2005, author = {Artiom Alhazov and Rudolf Freund}, title = {P Systems with One Membrane and Symport/Antiport Rules of Five Symbols are Computationally Complete}, booktitle = {Proceedings of the {T}hird {B}rainstorming {W}eek on {M}embrane {C}omputing}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {19--28}, abstract = {We consider P systems with only one membrane using symport/antiport rules and prove that any recursively enumerable set of k-dimensional vectors of natural numbers can be generated (accepted) by using at most k+4 symbols; hence any recursively enumerable set of natural numbers can be generated (accepted) by using at most five symbols.}, url = {http://www.gcn.us.es/3BWMC/Volumen.htm}, } @inproceedings{Alhazov.etal:tCarpet:ESF2005, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald}, title = {Tissue {P} Systems with Antiport Rules and Small Numbers of Symbols and Cells}, booktitle = {Proceedings of the {ESF} {E}xploratory {W}orkshop on {C}ellular {C}omputing ({C}omplexity {A}spects)}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {7--22}, abstract = {We consider tissue P systems with antiport rules and investigate their computational power when using only a (very) small number of symbols and cells. Even when using only one symbol, any recursively enumerable set of natural numbers can be generated with at most seven cells. 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 at most five symbols. Between these extreme cases of one symbol and one cell, respectively, there is a trade-off between the number of cells and the number of symbols, e.g. 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.}, eprint = {http://aartiom.50webs.com/articles/29fenix-7_ESF.pdf}, } @inproceedings{Alhazov.etal:OptMincoo2m:ESF2005, author = {Artiom Alhazov and Rudolf Freund and {\relax Yu}rii Rogozhin}, title = {Some Optimal Results on Symport/Antiport {P} Systems with Minimal Cooperation}, booktitle = {Proceedings of the {ESF} {E}xploratory {W}orkshop on {C}ellular {C}omputing ({C}omplexity {A}spects)}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {23--36}, abstract = {We prove that two classes of symport/antiport P systems with two membranes and with minimal cooperation, namely P systems with symport/antiport rules of size one and P systems with symport rules of size two, are computationally complete: (modulo the terminal alphabet) they generate all recursively enumerable sets of vectors of nonnegative integers. On the other hand, it is known that these systems with one membrane cannot be universal. Hence, the results we prove are optimal.}, eprint = {http://aartiom.50webs.com/articles/30fenix-23_ESF.pdf}, } @inproceedings{Alhazov.Verlan:SCarpetsDncoo:ESF2005, author = {Artiom Alhazov and Sergey Verlan}, title = {Sevilla Carpets of Deterministic Non-Cooperative {P} Systems}, booktitle = {Proceedings of the {ESF} {E}xploratory {W}orkshop on {C}ellular {C}omputing ({C}omplexity {A}spects)}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {53--60}, abstract = {A Sevilla carpet is a graphical representation of the sequence of multisets of rules applied at every step of the evolution of a P system. This paper is devoted to the research of the shape of Sevilla carpets. The case of deterministic non-cooperative systems is considered and a characterization of Sevilla carpets is given.}, eprint = {http://aartiom.50webs.com/articles/32fenix-53_ESF.pdf}, } @inproceedings{Alhazov.Rogozhin:Mincoo1m:BWMC2005, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin}, title = {Minimal Cooperation in Symport/Antiport {P} Systems with One Membrane}, booktitle = {Proceedings of the {T}hird {B}rainstorming {W}eek on {M}embrane {C}omputing}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {29--34}, abstract = {In this paper we consider symport/antiport P systems with one membrane and rules having at most two objects. Although it has been proved that only finite number sets can be generated by both OP_1(sym_2) (one-membrane systems with symport rules of weight at most 2) and OP_1(sym_1,anti_1) (one-membrane systems with symport/antiport rules of weight 1) the exact characterization is still an open question. We give some lower bounds, consider a few extensions, and state some open questions.}, url = {http://www.gcn.us.es/3BWMC/Volumen.htm}, } @inproceedings{Alhazov.etal:tSAmincoo:ESF2005, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin and Sergey Verlan}, title = {Symport/Antiport Tissue {P} Systems with Minimal Cooperation}, booktitle = {Proceedings of the {ESF} {E}xploratory {W}orkshop on {C}ellular {C}omputing ({C}omplexity {A}spects)}, address = {Sevilla, Spain}, publisher = {F{\'e}nix Editora}, year = {2005}, pages = {37--52}, abstract = {We investigate tissue P systems with symport/antiport with minimal cooperation, i.e., when only two objects may interact. We show that 2 cells are enough in order to generate all recursively enumerable sets of numbers. Moreover, the constructed systems simulate register machines and have a purely deterministic behavior. We also investigate systems with one cell and we show that they may generate only finite sets of numbers.}, eprint = {http://aartiom.50webs.com/articles/31fenix-37_ESF.pdf}, } @inproceedings{Rogozhin.Alhazov.Freund:SASurvey:PreWMC6:2005, author = {{\relax Yu}rii Rogozhin and Artiom Alhazov and Rudolf Freund}, title = {Computational Power of Symport/Antiport: History, Advances and Open Problems}, editor = {Rudolf Freund and Georg Lojka and Marion Oswald and {\relax Gh}eorghe P{\u a}un}, booktitle = {Pre-Proc. of the Sixth Workshop on Membrane Computing {WMC6}, Vienna, Austria}, year = {2005}, pages = {44-78}, abstract = {We first give a historical overview of the most important results obtained in the area of P systems and tissue P systems with symport / antiport rules especially with respect to the development of computational completeness results improving descriptional complexity parameters as the number of membranes and cells, respectively, and the weight of the rules as well as the number of objects. Then we establish our newest results: P systems with only one membrane and symport rules of weight three can generate any recursively enumerable language with only seven additional objects remaining in the skin membrane at the end of a halting computation; P systems with minimal cooperation, i.e., P systems with symport / antiport rules of size one and P systems with symport rules of weight two, are computationally complete with only two membranes with only three and six, respectively superfluous objects remaining in the output membrane at the end of a halting computation.}, url = {http://www.emcc.at/WMC6/WMC6PreProcFull.pdf}, } @inproceedings{Alhazov:PolarMinpar:PreWMC7:2006, author = {Artiom Alhazov}, title = {Minimal Parallelism and Number of Membrane Polarizations}, booktitle = {Pre-proceedings of Membrane Computing, International Workshop, WMC7}, year = {2006}, address = {Leiden, The Netherlands}, editor = {Hendrik-Jan Hoogeboom and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg}, pages = {74-87}, abstract = {It is known that the satisfiability problem (SAT) can be efficiently solved by a uniform family of P systems with active membranes with two polarizations working in a maximally parallel way. We study P systems with active membranes without non-elementary membrane division working in minimally parallel way. The main question we address is what number of polarizations is sufficient for an efficient computation depending on the types of rules used. In particular, we show that it is enough to have four polarizations sequential evolution rules changing polarizations, polarizationless nonelementary membrane division rules and polarizationless rules of sending an object out. The same problem is solved with the standard evolution rules, rules of sending an object out and polarizationless non-elementary membrane division rules, with six polarizations. It is an open question whether these numbers are optimal.}, url = {http://wmc7.liacs.nl/proceedings/listpapers.html}, } @inproceedings{Alhazov.etal:Extended_Spiking:PreWMC7:2006, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald and Marija Slavkovik}, title = {Extended Spiking Neural P Systems Generating Strings and Vectors of Non-Negative Integers}, booktitle = {Pre-proceedings of Membrane Computing, International Workshop, WMC7}, year = {2006}, address = {Leiden, The Netherlands}, editor = {Hendrik-Jan Hoogeboom and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg}, pages = {88-101}, abstract = {We consider extended variants of spiking neural P systems and show how these extensions of the original model allow for easy proofs of the computational completeness of extended spiking neural P systems and for the characterization of semilinear sets and regular languages by finite extended spiking neural P systems (defined by having only finite sets of rules assigned to the cells) with only a bounded number of neurons.}, url = {http://wmc7.liacs.nl/proceedings/listpapers.html}, } @inproceedings{Alhazov.Rogozhin:MinSA2mToChar:PreWMC7:2006, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin}, title = {Towards a Characterization of {P} Systems with Minimal Symport/Antiport and Two Membranes}, booktitle = {Pre-proceedings of Membrane Computing, International Workshop, WMC7}, year = {2006}, address = {Leiden, The Netherlands}, editor = {Hendrik-Jan Hoogeboom and {\relax Gh}eorghe P{\u a}un and Grzegorz Rozenberg}, pages = {102-118}, abstract = {We prove that any set of numbers containing zero generated by symport/antiport P systems with two membranes and minimal cooperation is finite (for both symport/antiport P systems and for purely symport P systems). On the other hand, one additional object in the output membrane allows symport/antiport P systems with two membranes and minimal cooperation generate any recursively enumerable sets of natural numbers without zero. The same question for symport P systems with two membranes and minimal cooperation (is only one additional object in the output membrane sufficient in order to get universality?) is still open.}, url = {http://wmc7.liacs.nl/proceedings/listpapers.html}, } @inproceedings{Alhazov:Encodings:BWMC2006, author = {Artiom Alhazov and Cosmin Bonchi{\c s} and Gabriel Ciobanu and Cornel Izba{\c s}a}, title = {Encodings and Arithmetic Operations in {P}~Systems}, booktitle = {Fourth Brainstorming Week on Membrane Computing, Sevilla January 30 - February 3, 2006. Volume I}, year = {2006}, publisher = {F{\'e}nix Editora}, editor = {Miguel Angel Guti{\'e}rrez-Naranjo and {\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Francisco-Jos{\'e} Romero-Campero}, pages = {1--28}, abstract = {Following [2], we present in this paper various number encodings and operations over multisets. We obtain the most compact encoding and several other interesting encodings and study their properties using elements of combinatorics over multisets. We also construct P systems that implement their associated operations. We quantify the effect of adding order to multiset thus obtaining a string, as going from encoding lengths of the number n in base b and time complexities of operations of the order n^(1/b) to lengths and complexities of order log_b(n).}, url = {http://www.gcn.us.es/4BWMC/4BWMC_proceedings.htm}, } @inproceedings{Alhazov.Perez:UniformQSAT:BWMC2006, author = {Artiom Alhazov and Mario de Jes{\'u}s P{\'e}rez-Jim{\'e}nez}, title = {Uniform Solution to {QSAT} Using Polarizationless Active Membranes}, booktitle = {Fourth Brainstorming Week on Membrane Computing, Sevilla January 30 - February 3, 2006. Volume I}, year = {2006}, publisher = {F{\'e}nix Editora}, editor = {Miguel Angel Guti{\'e}rrez-Naranjo and {\relax Gh}eorghe P{\u a}un and Agust{\'i}n Riscos-N{\'u}{\~n}ez and Francisco-Jos{\'e} Romero-Campero}, pages = {29--40}, abstract = {It is known that the satisfiability problem (SAT) can be solved a semi-uniform family of deterministic polarizationless P systems with active membranes with non elementary membrane division. We present a double improvement of this result by showing that the satisfiability of a quantified boolean formula (QSAT) can be solved by a uniform family of P systems of the same kind.}, url = {http://www.gcn.us.es/4BWMC/4BWMC_proceedings.htm}, } @inproceedings{Alhazov.etal:Partial:BWMC2007, author = {Artiom Alhazov and Rudolf Freund and Marion Oswald and Sergey Verlan}, title = {Partial Versus Total Halting in {P} Systems}, booktitle = {Proceedings of the Fifth Brainstorming Week on Membrane Computing}, publisher = {F{\'e}nix Editora}, year = {2007}, month = {January 29th - February 2}, address = {Sevilla (Spain)}, editor = {Miguel-Angel Guti{\'e}rrez-Naranjo and {\relax Gh}eorghe P{\u a}un and Alvaro Romero-Jim{\'e}nez and Agust{\'\i}n Riscos-N{\'u}{\~n}ez}, pages = {1--20}, 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 working in different derivation modes.}, url = {http://www.gcn.us.es/5BWMC/5BWMC_proceedings.htm}, } @inproceedings{Alhazov.Rogozhin:OutskinMinSA2m:PreWMC8:2007, author = {Artiom Alhazov and {\relax Yu}rii Rogozhin}, title = {Skin Output in {P} Systems with Minimal Symport/Antiport and Two Membranes}, booktitle = {Pre-proceedings of Membrane Computing, International Workshop - WMC8}, year = {2007}, address = {Thessaloniki, Greece}, editor = {George Eleftherakis and Petros Kefalas and {\relax Gh}eorghe P{\u a}un}, pages = {99--110}, abstract = {It is known that symport/antiport P systems with two membranes and minimal cooperation can generate any recursively enumerable sets of natural numbers using exactly one superfluous object in the output membrane where the output membrane is an elementary membrane. In this paper we consider symport/antiport P systems where the output membrane is the skin membrane. In this case we prove an unexpected characterization: symport/antiport P systems with two membranes and minimal cooperation generate exactly the recursively enumerable sets of natural numbers. The question about power of purely symport P systems with two membranes and minimal cooperation where the output membrane is the skin membrane is still open.}, url = {http://www.seerc.org/wmc8/procedings_web/PaperIndex.htm}, } @inbook{Alhazov.Sburlan:PSort:VAPS2005, author = {Artiom Alhazov and Drago{\c s} Sburlan}, title = {Static Sorting {P}~Systems}, year = {2005}, publisher = {Springer-Verlag}, pages = {215--252}, booktitle = {Applications of Membrane Computing}, editor = {Gabriel Ciobanu and {\relax Gh}eorghe P{\u a}un and Mario J. P{\'e}rez-Jim{\'e}nez}, abstract = {This chapter deals with the application of P systems to sorting problems. Traditional studies of sorting assume constant time for comparing two numbers and compute the time complexity with respect to the number of components of a vector to be sorted. Here, we assume the number of components to be a fixed number k, and study various algorithms based on different models of P systems and their time complexities with respect to the maximal number or to the sum of the numbers. Massively parallel computations that can be realized within the framework of P systems may lead to major improvements in solving the classical integer sorting problems. Despite this important characteristic, we will see that depending on the model used, the massive parallelism feature cannot be always used, and so some results will have complexities ``comparable'' with the classical integer sorting algorithms. Still, computing a word (ordered) from a multiset (unordered) can be a goal not only for computer science, but also, e.g. for biosynthesis (separating mixed objects according to some characteristics). Here, we will move from ranking algorithms that, starting with numbers represented as multisets, produce symbols in an order to effective sorting algorithms.}, url = {http://dx.doi.org/10.1007/3-540-29937-8_8}, } @proceedings{PreWMC:Tarragona:2004, editor = {Artiom Alhazov and Carlos Mart{\'i}n-Vide and {\relax Gh}eorghe P{\u a}un}, title = {Preproceedings of the Workshop on Membrane Computing Tarragona, July 17-22 2003}, year = {2003}, eprint = {http://psystems.disco.unimib.it/download/WMC03.zip}, url = {http://grlmc-dfilrom.urv.cat/grlmc/reports/WMC03.html}, } @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{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{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{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{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{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}, }