具有优先权的膜自动机

膜系统是由Gheorghe Paun受细胞生化特性启发而提出的一种分布式平行计算模型。该模型由有等级嵌入到最外层的外壳膜的膜组成，每一个膜划出一块可以包含物体的区域。这些物体对应于化学物质，在由膜限定的细胞器中发展和变化；物体可以穿过膜并摧毁膜。每一区域都有一套相关规则，物体依照这些规则发展或被运输到它们的母区域或子区域。     

具有突触规则的脉冲神经膜系统综述

膜系统是受到细胞、组织、器官和系统的结构和功能的启发而提出的一类生物启发式计算模型。具有突触规则的脉冲神经膜系统是一类受神经元间信息交流方式的启发而提出的膜系统,该类模型中神经元是存储信息的单元,突触是整合并传递信息的媒介,整个系统采用分布式、并行方式处理信息。文中回顾了具有突触规则的脉冲神经膜系统的定义及相关概念,介绍了若干个脉冲神经膜系统变体,并对比了各系统的同异;列出了该系统及其变体在不同工作模式下计算能力方面的研究进展,以及该系统在求解计算困难问题、算术运算和破解密码方面的应用;提出了尚待研究的若干问题,以期为具有突触规则的脉冲神经膜系统理论研究提供方向,同时为相关系统的应用研究拓展思路。     

小通用同质脉冲神经膜系统

最近,许多学者针对寻找基于脉冲神经膜系统的小通用计算设备问题进行了研究.脉冲神经膜系统是一种源于神经元之间通过电子脉冲传递信息方式的分布式、并行计算模型.同质脉冲神经膜系统是指一种系统中所有神经元具有相同规则集合的脉冲神经膜系统的受限变体.本文研究了同质脉冲神经膜系统的小通用性:在使用标准规则和权值情况下,作为计算函数的装置,需要53个神经元可以构造一个通用同质脉冲神经膜系统;作为产生数的装置,则需要52个神经元.     

通用的不带延迟的同质脉冲神经膜系统

脉冲神经膜系统是一种膜系统中吸收了脉冲神经网络特点的新型生物计算装置,具有强大的计算能力。同质脉冲神经膜系统是指一种所有神经元具有相同规则集合的脉冲神经膜系统的变体。研究了突触上带权值和突触上不带权值的两种同质脉冲神经膜系统在不使用具有延迟的激发规则情况下的计算通用性问题,并证明了这两种不带延迟的同质脉冲神经膜系统无论是工作在产生模式下,还是工作在接收模式下都是计算通用的。解决了曾湘祥、张兴义和潘林强提出的关于不带延迟的同质脉冲神经膜系统是否具有计算通用性的公开问题。     

脉冲神经膜系统在穷举使用规则下产生的二进制字符串语言

脉冲神经膜系统是基于大脑中神经元之间通过突触相瓦协作、处理脉冲的生物现象提出的一种新的模型,文中在穷举使用规则的情况下考虑将脉冲神经膜系统作为串语言产生器:当输出神经元发送出一个或多个神经脉冲时,用数字1表示,否则用数字0表示,当计算停止时,把产生的二进制串定义为系统的计算结果.在文中,作者让明了在穷举使用规则的情况下,具有一个神经元的脉冲神经膜系统可以刻画二进制有限语言,并且证明了在不限制神经元个数的情况下,该系统可以刻画递归可枚举语言.     

带反脉冲的同质脉冲神经膜系统

脉冲神经膜系统是一种膜系统中吸收了脉冲神经网络特点的新型生物计算装置,具有强大的计算能力.带反脉冲的同质脉冲神经膜系统是使用了两种对象(称为脉冲和反脉冲)、且其中每个神经元具有相同规则集合的一种脉冲神经膜系统的变体.本文研究了无延迟规则和突触权值情况下的带反脉冲同质脉冲神经膜系统的计算通用性问题,证明了这种P系统无论是工作在产生模式,还是接收模式下都是计算通用的.本文解答了曾湘祥等人提出的关于是否存在无延迟规则的同质脉冲神经膜系统和如何移除突触权值的两个公开问题.     

全局异步局部同步的带阈值的脉冲神经膜系统

带阈值的脉冲神经膜系统是一类生物启发式计算模型，提出该系统的灵感来自神经元电位变化与其活动的联系。对于带阈值的脉冲神经膜系统的计算能力研究，人们已证明该系统在极大同步工作模式下，作为产生数或接受数的计算设备时，是与图灵机等价(计算通用)的，而该系统在其他工作模式下的计算能力如何也是人们普遍关心的问题。文中研究的是带阈值脉冲神经膜系统在全局异步局部同步模式下产生数的能力，证明了突触带整数权重的相应系统是计算通用的，而突触带正整数权重的相应系统只能产生半线性数集。研究结果表明，突触权重的取值范围影响着全局异步局部同步工作模式下带阈值脉冲神经膜系统的计算能力。     

基于膜系统的逻辑运算研究

膜系统是在细胞层次上模仿自然过程的一种计算模型,最大的优点是可以以极大的并行度来进行计算。该文证明了执行逻辑运算在膜系统中的可能性,并给出了一个有效的方法来实施逻辑运算,这相对比在一般计算机体系结构中执行要简单。     

基于膜系统的逻辑运算研究

膜系统是在细胞层次上模仿自然过程的一种计算模型,最大的优点是可以以极大的并行度来进行计算。该文证明了执行逻辑运算在膜系统中的可能性,并给出了一个有效的方法来实施逻辑运算,这相对比在一般计算机体系结构中执行要简单。     

一种基于膜计算的遗传算法图像分割方法

提出了一种基于膜计算的改进遗传算法图像分割方法。设计了一个三层膜的细胞型P系统,各个膜通过运行进化规则和交流规则进行寻优。该算法融合了P系统的极大并行性与遗传算法的良好收敛性,并通过与传统遗传算法、Otsu法的实验比较验证了所提出的图像分割方法的可行性与有效性。     

A uniform solution to the independent set problem through tissue P systems with cell separation

Membrane computing is an emergent branch of natural computing, which is inspired by the structure and the functioning of living cells, as well as the organization of cells in tissues, organs, and other higher order structures. Tissue P systems are a class of the most investigated computing models in the framework of membrane computing, especially in the aspect of efficiency. To generate an exponential resource in a polynomial time, cell separation is incorporated into such systems, thus obtaining so called tissue P systems with cell separation. In this work, we exploit the computational efficiency of this model and construct a uniform family of such tissue P systems for solving the independent set problem, a well-known NP-complete problem, by which an efficient solution can be obtained in polynomial time.     

Tissue P systems with cell separation: attacking the partition problem

Tissue P systems are distributed parallel and non-deterministic computing models in the framework of membrane computing, which are inspired by intercellular communication and cooperation between neurons. Recently, cell separation is introduced into tissue P systems, which enables systems to generate an exponential workspace in a polynomial time. In this work, the computational power of tissue P systems with cell separation is investigated. Specifically, a uniform family of tissue P systems with ce...     

Solving HPP and SAT by P Systems with Active Membranes and Separation Rules

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.     

A polynomial alternative to unbounded environment for tissue P systems with cell division

The standard definition of tissue P systems includes a special alphabet whose elements are assumed to appear in the initial configuration of the system in an arbitrarily large number of copies. These objects reside in a distinguished place of the system, called the environment. Such potentially infinite supply of objects seems an unfair tool when designing efficient solutions to computationally hard problems in the framework of membrane computing, by performing a space–time trade-off. This paper deals with computational aspects of tissue P systems with cell division where there is no environment having the property mentioned above. Specifically, we prove that the polynomial complexity classes associated with tissue P systems with cell division and with or without environment are actually identical. As a consequence, we conclude that it is not necessary to have infinitely many copies of some objects in the initial configuration in order to solve NP–complete problems in an efficient way.     

P systems with active membranes: trading time for space

We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules, are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential time and polynomial space problems that cannot be solved in polynomial time, unless P = SPACE.     

Homogenous spiking neural P systems with anti-spikes

Spiking neural P systems with anti-spikes (ASN P systems, for short) are a class of neural-like computing models in membrane computing, which are inspired by neurons communication through both excitatory and inhibitory impulses (spikes). In this work, we consider a restricted variant of ASN P systems, called homogeneous ASN P systems, where any neuron has the same set of spiking and forgetting rules. As a result, we prove that such systems can achieve Turing completeness. Specifically, it is proved that two categories of pure form of spiking rules (for a spiking rule, if the language corresponding to the regular expression that controls its application is exactly the form of spikes consumed by the rule, then the rule is called pure) are sufficient to compute and accept the family of sets of Turing computable natural numbers.     

P Systems with Mobile Membranes

P systems with active membranes are among the central ones in membrane computing, and they were shown to be both computationally universal (able to simulate Turing machines) and computationally efficient (able to solve hard problems in polynomial time). However, in all cases, these results were obtained by making use of several powerful features, such as membrane polarization, label changing, division of non-elementary membranes, priorities, or cooperative rules. This paper contributes to the research effort of introducing a class of P systems with active membranes having none of the features mentioned above, but still preserving the power and the efficiency. The additional feature we consider instead are the operations of endocytosis and exocytosis: moving a membrane inside a neighboring membrane, or outside the membrane where it is placed. We investigate the power and the efficiency of these systems (also using membrane division) by first proving that they can simulate (with a linear slowdown and without introducing non-determinism) rewriting P systems with 2-replication, for which the universality and the possibility of solving NP-complete problems in polynomial time are known. In this way, the universality and efficiency are also obtained for our systems. We also give a direct and simple proof for the universality result – without using division rules (the proof uses nine membranes, but we do not know whether this number can be decreased).     

Spiking neural P systems with neuron division and budding

Spiking neural P systems are a class of distributed and parallel computing models inspired by spiking neurons.In this work,the features of neuron division and neuron budding are introduced into the framework of spiking neural P systems,which are processes inspired by neural stem cell division. With neuron division and neuron budding,a spiking neural P system can generate exponential work space in polynomial time as the case for P systems with active membranes.In this way,spiking neural P systems can efficie...     

Efficient simulation of tissue-like P systems by transition cell-like P systems

In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time. Working with P systems whose membrane structure does not increase in size, it is known that it is not possible to solve computationally hard problems (unless P = NP), basically due to the impossibility of constructing exponential number of membranes, in polynomial time, using only evolution, communication and dissolution rules. In this paper we show how a family of recognizer tissue P systems with symport/antiport rules which solves a decision problem can be efficiently simulated by a family of basic recognizer P systems solving the same problem. This simulation allows us to transfer the result about the limitations in computational power, from the model of basic cell-like P systems to this kind of tissue-like P systems.     

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.