Repetitiveness of languages generated by morphisms

We study the repetition of subwords in languages generated by morphisms. Fundamental to our approach is the notion of quasi-repetitive elements. Using these elements we present a new characterization for repetitive morphisms, from which we derive a simple proof for the fact that a D0L-language is repetitive if and only if it is strongly repetitive (Ehrenfeucht and Rozenberg, Inform. and Control 59 (1983) 13–35). From this proof we obtain a structurally simple polynomial-time algorithm for deciding whether such a language is repetitive. From further results on quasi-repetitive elements we obtain as a consequence a complete characterization for all those morphisms on a two-letter alphabet that are repetitive, a result which is closely related to a result of Séébold (Bull. EATCS 36 (1988) 137–151) on the D0L periodicity problem. Finally, we characterize those morphisms f on a two-letter alphabet, for which the language L(f) generated by f or the language SL(f) of subwords of L(f) are context-free or even regular.     

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.     

基于单符号统计的简单L系统反演约束研究

给出一串已知的L系统符号串，以便从中寻找出能够通过L系统迭代生长复原的L基因组是目前L系统研究领域的逆向工作，为了能更好地进行逆向迭代，首先从研究符合串中的单符号统计规律入手，进而通过对在L系统的迭代生长中，单种符号数量发生有规律地变化进行的研究，提出了一些较有价值的符号统计关系式；然后在进行L符号串反演时，根据这些关系式，不仅能够缩小寻找逆向L基因组的范围，并能判定逆向L基因组的正确笥，从而为快速实现L系统符号串反演成L基因组，提供了较强有力的判据和可能性，而且这些关系式还 与其他搜索算法（如遗传算法）配合使用快的获得搜索结果。     

自然计算的新分支——膜计算

作为自然计算的新分支,膜计算是当前计算机科学、数学、生物学和人工智能等多学科交叉的研究热点.概述膜计算的最新动态,以一个简单膜系统为例介绍膜计算的基本概念和基本原理,从细胞型、组织型和神经型三类膜系统以及它们的计算能力和计算效率方面介绍膜计算理论研究进展,通过概括膜计算国内外应用研究成果讨论其应用前景和方向,并从软硬件发展历程分析膜系统软硬实现研究现状.最后给出有关膜计算研究的重要网络资源、热点研究领域和重点关注的问题.     

Small universal simple spiking neural P systems with weights

Spiking neural P systems with weights（WSN P systems,for short） are a new variant of spiking neural P systems,where the rules of a neuron are enabled when the potential of that neuron equals a given value.It is known that WSN P systems are universal by simulating register machines. However,in these universal systems,no bound is considered on the number of neurons and rules. In this work,a restricted variant of WSN P systems is considered,called simple WSN P systems,where each neuron has only one rule. The complexity parameter,the number of neurons,to construct a universal simple WSN P system is investigated. It is proved that there is a universal simple WSN P system with 48 neurons for computing functions; as generator of sets of numbers,there is an almost simple（that is,each neuron has only one rule except that one neuron has two rules） and universal WSN P system with 45 neurons.     

The computational power of cell division in P systems: Beating down parallel computers?

We study the computational power of cell division operations in the formalframework of P systems, a mathematical model of cell-like membrane structure with regulated transport of objects (molecules) through membranes. We show that a uniformfamily of P systems with active membranes and2-division is able to solve the well-known PSPACE-complete problem QBF inlinear time. This result implies that such a family of P systems modelling celldivision is at least as powerful as so-called Second Machine Class computers. The Second Machine Class, containing most of the fundamental parallelcomputer models such as parallel RAM machines of types SIMD and MIMD, vector machinesand others, is characterized by using an exponential amount of resources(processing units) with respect to the computing time.     

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...     

分形在激光全息防伪系统中的应用研究

将激光全息制品与分形图案相结合，大大增强了防伪效果．通过对林氏分形算法伪码表示及IFS迭代函数系统的研究，完成了分形算法组件，可以根据特定的光刻硬件规则，产生可直接驱动激光打印光刻硬件的数据文件．     

Unexpected universality results for three classes of P systems with symport/antiport

Symport and antiport are biological ways of transporting molecules through membranesin ``collaborating' pairs; in the case of symport the two molecules pass in the same direction, in the case of antiport the two molecules pass in opposite directions. Here we first survey the results about the computing power of membrane systems (P systems) using only symport/antiport rules (hence these systems compute by communication only), then we consider a recently introduced, way of defining the result of a computation in a membrane system: looking for the trace of certain objects in their movement through membranes. Rather unexpected, in this way we get characterizations of recursively enumerable languages by means of membrane systems with symport/antiport which work with multisets of objects (note the qualitative difference between the data structure used by computations – multisets: no ordering– and the data structure of the output – strings: linear ordering). A similar remark holds true for the case of analysing P systems, which work in an automata-like manner: the sequence of certain distinguished objects taken from the environment during acomputation is the string recognized by the computation. We also survey universality results from this area, with sketched proofs. Some open problems are also formulated. This revised version was published online in June 2006 with corrections to the Cover Date.     

A quick overview of membrane computing with some details about spiking neural P systems

We briefly present the basic elements of membrane computing, a branch of natural computing inspired by the structure and functioning of living cells, then we give some details about spiking neural P systems, a class of membrane systems recently introduced, with motivations related to the way neurons communicate by means of spikes. In both cases, of general P systems and of spiking neural P systems, we introduce the fundamental concepts, give a few examples, then recall the types of results and of applications. A series of bibliographical references are provided.     

完备剩余格上的蕴涵闭包系统

在完备剩余格上引入了蕴涵闭包系统的概念,讨论了蕴涵闭包系统与闭包系统之间的关系。给出了蕴涵闭包系统的一些性质及其表示定理。进一步研究了蕴涵闭包算子和蕴涵闭包系统的关系。     

Restricted ambiguity of erasing morphisms

A morphism h is called ambiguous for a string s if there is another morphism that maps s to the same image as h; otherwise, it is called unambiguous. In this paper, we examine some fundamental problems on the ambiguity of erasing morphisms. We provide a detailed analysis of so-called ambiguity partitions, and our main result uses this concept to characterise those strings that have a morphism of strongly restricted ambiguity. Furthermore, we demonstrate that there are strings for which the set of unambiguous morphisms, depending on the size of the target alphabet of these morphisms, is empty, finite or infinite. Finally, we show that the problem of the existence of unambiguous erasing morphisms is equivalent to some basic decision problems for nonerasing multi-pattern languages.     

Forbidding and enforcing in membrane computing

Motivated by biochemistry and the non-deterministic reactions between molecules,the authors in (Ehrenfeucht and Rozenberg, 2003) introduced the concept of forbidding-enforcing systems(fe-systems) that define families of languages. Using the same concept we propose to study forbidding and enforcing within membrane systems. Two approaches are presented; in the first case the membrane system generates families of languages and in the second casethe membrane system generates a single language. We show that by using forbidding-enforcing in membranes, families of languages that cannot be defined by any fe-system can be generated. When a single language is generated, we show that SAT can be solved in a constant time (at price of using an exponential space). Also we show an example of a context-free language that can be generated without any forbidders.     

Membrane automata with priorities

In this paper the one-way P automata with priorities are introduced. Such automata are P systems where the membranes are only allowed to consume objects from parent membranes, under the given conditions. The result of computation of these systems is the set of multiset sequences consumed by skin membrane into the system. The rules associated in some order with each membrane cannot modify any objects, they can only move them through membrane. We show that P automata with priorities and two membranes can accept every recursively enumerated language.     

一种带混合进化机制的膜聚类算法

膜计算(也称为P系统或膜系统)是一种新颖的分布式、并行计算模型.为了处理数据聚类问题,提出了一种采用混合进化机制的膜聚类算法.它使用了一个由3个细胞组成的组织P系统,为一个待聚类的数据集发现最优的簇中心.其对象表示候选的簇中心,并且这3个细胞分别使用了3种不同的进化机制:遗传算子、速度-位移模型和差分进化机制.然而,所使用的速度-位移模型和差分进化机制是结合了这个特殊膜结构和转运机制所提出的改进版本.这种混合进化机制能够增强系统中对象的多样性和改善收敛性能.在混合进化机制和转运机制控制下,这种膜聚类算法能够确定一个数据集的良好划分.所提出的膜聚类算法在3个人工数据集和5个真实数据集上被评估,并与k-means和几种进化聚类算法进行比较.统计显著性测试建立了所提出的膜聚类算法的优势.     

采用dsDNA-MC优化的非线性系统预测控制

将基于DNA双链结构的膜计算优化方法（dsDNA-MC）用于输入受限的非线性预测控制器设计,提出了基于dsDNA-MC优化的非线性系统预测控制算法。在对单输入单输出非线性系统预测控制分析的基础上,将非线性系统预测控制问题归结为具有输入约束的非线性系统优化问题,并采用dsDNA-MC算法来求解这一问题。仿真结果表明该算法可行、有效。     

On the transformation of symmetric sparse matrices to the triple diagonal form

The problem of minimizing the number of zero elements that become non-zero during the computation when a sparse symmetric matrix is reduced to a triple diagonal form, either by Givens' or Householder's method, is discussed. Algorithms for minimizing the growth of such non-zero elements are given.