P systems with local graph productions

P systems (membrane systems) of various types so far mainly have been considered as computing devices working on multisets or strings. In this paper we investigate P systems with local graph productions generating weakly connected directed graphs. At least when equipped with a priority relation on the rules, such P systems can generate any recursively enumerable language of weakly connected directed graphs with only one membrane. Rudolf Freund, Ph.D.: He holds a master and doctor degree in computer science and a master degree in mathematics and physics. Since 1995 he is Associate Professor at the Vienna University of Technology in Austria. His research interests include array and graph grammars, regulated rewriting, infinite words, syntactic pattern recognition, neural networks, and especially models and systems for biological computing. In these fields, he is author or co-author of more than ninety scientific papers. Marion Oswald, Ph.D.: She received her master and doctor degree in computer science from the Vienna University of Technology, Austria, in 2001 and 2003, respectively. Her research interests include but are not limited to artificial life as well as models and systems for biological computing, in which fields she is author or co-author of more than fifteen scientific papers.     

Languages generated by P systems with active membranes

We propose an alternative approach to generate languages by means of P systems: building up an appropriate representation for a string by means of a corresponding membrane structure and then generating the string by visiting the membrane structure according to a well-specified strategy. To this aim, we consider P systems with active membranes, allowing membrane creation or division or duplication and dissolution, where the output of a computation may be obtained either by visiting the tree associated with the membrane structure, or by following the traces of a specific object, called traveller, or sending out the objects. For each of these approaches, we provide characterizations of recursively enumerable languages based on P systems that use different sets of operations for modifying the membrane structure. Francesco Bernardini: He started his Ph.D. at the University of Sheffield in December 2002 after having previously got a master degree in Computer Science from the University of Pisa in Italy. His research is dedicated to the study of theoretical aspects of membrane computing (P systems) and discrete models of biological systems based on P systems. Marian Gheorghe, Ph.D.: His main research interests are in computational models and their applications to software modelling and testing, formal specifications of agent based systems, software engineering. He was investigating computational power of various generative devices (regular, context-free, fully initial; grammar systems; L-systems and variants). He is currently interested in natural computing (membrane calculus) and biological modelling.     

Hierarchies of parallel rewriting P systems — A survey

The paper is about some families of rewriting P systems, where the application of evolution rules is extended from the classical sequential rewriting to the parallel one (as, for instance, in Lindenmayer systems). As a result, consistency problems for the communication of strings may arise. Three variants of parallel rewriting P systems (already present in the literature) are considered here, together with the strategies they use to face the communication problem, and some parallelism methods for string rewriting are defined. We give a survey of all known results about each variant and we state some relations among the three variants, thus establishing hierarchies of parallel rewriting P systems. Various open problems related to the subject are also presented. Danicla Besozzi: She is assistant professor at the University of Milano. She received her M.S. in Mathematics (2000) from the University of Como and Ph.D. in Computer Science (2004) from the University of Milano. Her research interests cover topics in Formal Language Theory, Molecular Computing, Systems Biology. She is member of EATCS (European Association for Theoretical Computer Science) and EMCC (European Molecular Computing Consortium). Giancarlo Mauri: He is full professor of Computer Science at the University of Milano-Bicocca. His research interests are mainly in the area of theoretical computer science, and include: formal languages and automata, computational complexity, computational learning theory, soft computing techniques, cellular automata, bioinformatics and molecular computing. On these subjects, he published more than 150 scientific papers in international journals, contributed volumes and conference proceedings. Claudio Zandron: He received Ph.D. in Computer Science at the University of Milan, Italy, in 2001. Since 2002 he is assistant professor at the University of Milano-Bicocca, Italy. He is member of the EATCS (European Association for Theoretical Computer Science) and of EMCC (European Molecular Computing Consortium). His research interests are Molecular Computing (DNA and Membrane Computing) and Formal Languages.     

P systems with active membranes and without polarizations

P systems with active membranes but without using electrical charges (polarizations) are shown to be complete for generating recursively enumerable string languages when working on string objects and using only rules with membrane transitions as well as rules with membrane dissolving and elementary membrane division, but also when using various other kinds of rules, even including a new type of rules allowing for membrane generation. In particular, allowing for changing membrane labels turns out to be a very powerful control feature.     

On the power of elementary features in spiking neural P systems

Since their first publication in 2006, spiking neural (SN) P systems have already attracted the attention of a lot of researchers. This might be owing to the fact that this abstract computing device follows basic principles known from spiking neural nets, but its implementation is discrete, using membrane computing background. Among the elementary properties which confer SN P systems their computational power one can count the unbounded fan-in (indegree) and fan-out (outdegree) of each “neuron”, synchronicity of the whole system, the possibility of delaying and/or removing spikes in neurons, the capability of evaluating arbitrary regular expressions in neurons in constant time and some others. In this paper we focus on the power of these elementary features. Particularly, we study the power of the model when some of these features are disabled. Rather surprisingly, even very restricted SN P systems keep their universal computational power. Certain important questions regarding this topic still remain open.     

The power of communication: P systems with symport/antiport

In the attempt to have a framework where the computation is done by communication only, we consider the biological phenomenon of trans-membrane transport of couples of chemicals (one say symport when two chemicals pass together through a membrane, in the same direction, and antiport when two chemicals pass simultaneously through a membrane, in opposite directions). Surprisingly enough, membrane systems without changing (evolving) the used objects and with the communication based on rules of this type are computationally complete, and this result is achieved even for pairs of communicated objects (as encountered in biology). Five membranes are used; the number of membranes is reduced to two if more than two chemicals may collaborate when passing through membranes. Andrei Paun: He graduated the Faculty of Mathematics of Bucharest University in 1998, received his M.Sc. degree from The University of Western Ontario in 1999, and since then he is a PhD student in the Computer Science Department of University of Western Ontario, London, Canada (under the guidance of prof. Sheng Yu). The topic of his thesis is Molecular Computing (especially, DNA and Membrane Computing), but his research interests also include neural networks, implementing automata, combinatorics on words. Gheorghe Paun: (the proud father of two sons, including the first author of this paper) He is a member of the Romanian Academy, working as a senior researcher in the Institute of Mathematics of the Romanian Academy, Bucharest, and as a Ramon y Cajal researcher in Rovira i Virgili University of Tarragona, Spain. He is one of the most active authors in (the theory of) DNA Computing, (co)author of many papers in this area, (co)author and (co)editor of several books. In 1998 he has initiated the area of Membrane Computing. Other research interests: regulated rewriting, grammar systems, contextual grammars, combinatorics on words, computational linguistics.     

On a class of P automata

In this paper, we propose a class of P automata in which each membrane has a state, like in tissue P systems [5], and the computation starts at some initial state and ends in a final state. Unlike the automaton considered in [2], where rules are used in sequential manner, here we consider a variant such that the rules can be applied in maximal mode (as defined in tissue P systems). We show that P automata characterize the recursively enumerable sets of vectors of natural numbers.     

Results on catalytic and evolution-communication P systems

In this paper we give several improved universality results for two important classes of P systems: P systems with catalysts and evolution-communication P systems. First, the result from Reference,¹⁴⁾ stating that six catalysts ensure the universality, has been improved in two ways: using bistable catalysts and using moving catalysts. Specifically, the universality can be reached with one bistable catalyst and 2 usual catalysts (using five membranes), as well as with one moving catalyst and three membranes, or with two moving catalysts and only two membranes. The second part of the paper deals with evolution-communication P systems, and we also give improved universality results for this type of systems, in terms of the weight of symport/antiport rules, number of membranes, or number of catalysts. Shankara Narayanan Krishna: She is an Assistant Professor in Dept. Computer Science & Engg, IIT Bombay, India. Her research interests are Natural Computing and Formal Methods. Andrei Paun, Ph.D.: He obtained his bachelor degree in Mathematics and Computer Science from the University of Bucharest, Romania. He obtaind his Ph.D. degree in Computer Science, at University of Western Ontario, Canada, under the supervision of Prof. Dr. Sheng Yu, with the thesis “Unconventional Models of Computation: DNA and Membrane Computing”. After graduation he received a postdoctoral felloship from NSERC, Canada and after six months he accepted an assistant professor position in US at Louisiana Tech University.     

Minimizing evolution-communication P systems and automata

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,¹⁾ 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. Artiom Alhazov: He has graduated from Mathematics and Computer Science, State University of Moldova in 2001, and is currently a Ph.D. student in Chişinăm, Moldova, and Tarragona, Spain. He has won prizes at 3 National Olympiads in Informatics and in Mathematics (1995 and 1996), participated at 8th International Olympiad in Informatics (Veszprem, Hungary, 1996). He has experience in programming and teaching, and has published 18 papers, mostly in Membrane Computing. His interests are Origami, Mathematics, Programming, Theoretical Computer Science, Formal Linguistics and Biocomputing.     

Power and size of extended Watson–Crick L systems

A Watson–Crick D0L system is a language-theoretic model which is based on a D0L system and a letter-to-letter morphism, representing the Watson–Crick complementarity phenomenon of DNA. The two components are connected by a triggering mechanism. The computational capacity of these constructs is of particular interest. In this paper we prove that if the underlying systems are EDT0L systems or E0L systems, then these constructs are able to generate any recursively enumerable language. Moreover, to reach this power, Watson–Crick EDT0L systems with either two tables or a bounded number of non-terminals suffice.     

Solving the Subset-Sum problem by P systems with active membranes

We present the first membrance computing solution to the Subset-Sum problem using a family of deterministic P systems with active membranes. We do not use priority among rules, membrane dissolution nor cooperation; it suffices to control the electrical charges of the membranes and to introduce some counters. The number of steps of any computation is of the linear order (but it is necessary a polynomial-time of precomputed resources).     

Computing using signals: from cells to P systems

In cell biology a fundamental topic is the study of how biological signals are managed by cells. Signals can arise from inside the cell or from the external environment and the correct answer to certain signals is essential for bacteria to survive in a certain environment. Starting from these biological motivations we consider a model of P systems where the computation is controlled by signals which move across the regions. In particular, we consider signals-based P systems where the symbol-objects cannot be moved and the evolution rules can be activated/inactivated using a finite number of signals (signal-promoters) moved across the membranes; differently from standard P systems using promoters, in our case signal-promoters cannot be created during the computation. After discussing the biological motivations we show how this model becomes universal when it uses one catalyst and a bounded number of signal-promoters. Also results concerning signals-based P systems using non cooperative rules together with several open problems are presented.     

A Prolog simulator for deterministic P systems with active membranes

In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in each step of the evolution as literals of an appropriate language of first order logic. We provide a Prolog program to simulate, the evolution of these P systems and present some auxiliary tools to simulate the evolution of a P system with active membranes using 2-division which solves the SAT problem following the techniques presented in Reference.¹⁰ Andrés Cordón-Franco: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Mathematical Logic, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical (software implementation) point of view. Miguel A. Gutiérrez-Naranjo: He is an assistant professor in the Computer Science and Artificial Intelligence Department at University of Sevilla, Spain. He is also a member of the Research Group on Natural Computing of the University of Seville. His research interest includes Machine Learning, Logic Programming and Membrane Computing, both from a theoretical and a practical point of view. Mario J. Pérez-Jiménez, Ph.D.: He is professor of Department of Computer Science and Artificial Intelligence at University of Seville, where he is the head of the Group of Research on Natural Computing, He has published 8 books of Mathematics and Computation, and more than 90 scientific articles in prestigious scientific journals. He is member of European Molecular Computing Consortium. Fernando Sancho-Caparrini: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Complex Systems, DNA Computing, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical point of view.     

Region-based segmentation of 2D and 3D images with tissue-like P systems

Membrane Computing is a biologically inspired computational model. Its devices are called P systems and they perform computations by applying a finite set of rules in a synchronous, maximally parallel way. In this paper, we develop a variant of P-system, called tissue-like P system in order to design in this computational setting, a region-based segmentation algorithm of 2D pixel-based and 3D voxel-based digital images. Concretely, we use 4-adjacency neighborhood relation between pixels in 2D and 6-adjacency neighborhood relation between voxel in 3D for segmenting digital images in a constant number of steps. Finally, specific software is used to check the validity of these systems with some simple examples.     

Spiking neural P systems with extended rules: universality and languages

We consider spiking neural P systems with rules allowed to introduce zero, one, or more spikes at the same time. The motivation comes both from constructing small universal systems and from generating strings; previous results from these areas are briefly recalled. Then, the computing power of the obtained systems is investigated, when considering them as number generating and as language generating devices. In the first case, a simpler proof of universality is obtained, while in the latter case we find characterizations of finite and recursively enumerable languages (without using any squeezing mechanism, as it was necessary in the case of standard rules). The relationships with regular languages are also investigated.     

On the power of enzymatic numerical P systems

We study the computing power of a class of numerical P systems introduced in the framework of autonomous robot control, namely enzymatic numerical P systems. Three ways of using the evolution programs are investigated: sequential, all-parallel and one-parallel (with the same variable used in all programs or in only one, respectively); moreover, both deterministic and non-deterministic systems are considered. The Turing universality of some of the obtained classes of numerical P systems is proved (for polynomials with the smallest possible degree, one, also introducing a new proof technique in this area, namely starting the universality proof from the characterization of computable sets of numbers by means of register machines). The power of many other classes remains to be investigated.     

关系模式规范化的方法探讨及实例分析

提出了关系模式规范化的方便可行的方法.     

A classification of the expressive power of well-structured transition systems

We compare the expressive power of a class of well-structured transition systems that includes relational automata (extensions of), Petri nets, lossy channel systems, constrained multiset rewriting systems, and data nets. For each one of these models we study the class of languages generated by labeled transition systems describing their semantics. We consider here two types of accepting conditions: coverability and reachability of a fixed a priori configuration. In both cases we obtain a strict hierarchy in which constrained multiset rewriting systems is the most expressive model.     

Parallel and distributed computing models on a graphics processing unit to accelerate simulation of membrane systems

Membrane systems are parallel distributed computing models that are used in a wide variety of areas. Use of a sequential machine to simulate membrane systems loses the advantage of parallelism in Membrane Computing. In this paper, an innovative classification algorithm based on a weighted network is introduced. Two new algorithms have been proposed for simulating membrane systems models on a Graphics Processing Unit (GPU). Communication and synchronization between threads and thread blocks in a GPU are time-consuming processes. In previous studies, dependent objects were assigned to different threads. This increases the need for communication between threads, and as a result, performance decreases. In previous studies, dependent membranes have also been assigned to different thread blocks, requiring inter-block communications and decreasing performance. The speedup of the proposed algorithm on a GPU that classifies dependent objects using a sequential approach, for example with 512 objects per membrane, was 82×, while for the previous approach (Algorithm 1), it was 8.2×. For a membrane system with high dependency among membranes, the speedup of the second proposed algorithm (Algorithm 3) was 12×, while for the previous approach (Algorithm 1) and the first proposed algorithm (Algorithm 2) that assign each membrane to one thread block, it was 1.8×.     

白蚁虫害仿真预测系统中反规范化的应用

白蚁虫害仿真预测系统中所应用的数据库首先都是基于规范化原则设计的,但考虑到效率的问题,就按照数据仓库中的反规范化原则对数据库进行了改进.本文在简要介绍了数据库中反规范化的应用后,详细地举出了一个用反规范化设计的数据库来讨论如何通过反规范化进行数据库设计优化.