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