Minimization strategies for maximally parallel multiset rewriting systems

Maximally parallel multiset rewriting systems (MPMRS) give 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 Turing universal; however, a direct translation leads to quite a large 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) [9]) 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 those systems.     

A hybrid approach based on differential evolution and tissue membrane systems for solving constrained manufacturing parameter optimization problems

This paper presents a hybrid approach based on appropriately combining Differential Evolution algorithms and Tissue P Systems (DETPS for short), used for solving a class of constrained manufacturing parameter optimization problems. DETPS uses a network membrane structure, evolution and communication rules like in a tissue P system to specify five widely used DE variants respectively put inside five cells of the tissue membrane system. Each DE variant independently evolves in a cell according to its own evolutionary mechanism and its parameters are dynamically adjusted in the process of evolution. DETPS applies the channels connecting the five cells of the tissue membrane system to implement communication in the process of evolution. Twenty-one benchmark problems taken from the specialized literature related to constrained manufacturing parameter optimization are used to test the DETPS performance. Experimental results show that DETPS is superior or competitive to twenty-two optimization algorithms recently reported in the literature.     

带膜分裂和促进剂的通讯膜系统求解QSAT问题

膜计算是自然计算的一个分支,膜计算中所研究的模型均称为膜系统,而细胞间通讯是膜系统的一个重要特征。带膜分裂的通讯膜系统是一种分布式并行计算模型,可以在多项式时间内解决计算困难问题。文中将促进剂引入带膜分裂的类细胞型通讯膜系统,提出了膜系统的一种变型——带膜分裂和促进剂的通讯膜系统,其中,一个促进剂可以同时控制多条规则,而促进剂本身不参与该条规则的进化。文中研究了带膜分裂和促进剂的通讯膜系统的计算效率,证明该类膜系统在使用同向规则长度为2,每条规则中促进剂的个数最多为1时,可以在多项式时间内求解PSPACE完全问题(QSAT问题)的统一解。     

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.     

Independent agents in a globalized world modelled by tissue P systems

For modelling the interactions of independent agents (only interacting via a common environment, but not depending on any direct physical interactions with other agents) in the globalized world, we here consider so-called agent tissue P systems (ATP systems). Based on the model of tissue P systems, such ATP systems consist of cells (independent agents) with specific programs which allow for changing the objects inside the agent or for exchanging objects from inside the agent with objects from the environment through the cell membrane. We investigate the computational power of specific variants of ATP systems, and also discuss the special decidability problem whether or not a given ATP system of a specific type from its initial contents can ever reach a configuration where all objects in the system are contained in a specific subset of the set of objects.     

One-membrane symport with few extra symbols

Membrane systems (with symbol objects) are formal models of distributed parallel multiset processing. Symport rules move multiple objects to a neighbouring region. It is known that for P systems with symport rules of weight at most 3 and a single membrane, seven superfluous symbols are enough for computational completeness, and one is necessary. We present the improvements of the lower bounds on the generative power of P systems with symport of weight bounded by 3 and 4, in particular, establishing that six and two extra symbols suffice, respectively. Besides maximally parallel P systems, we also consider sequential ones. In fact, all presented non-universality lower bound results, together with all upper bound results, hold also in this case, yielding the current state of the art.     

Multiset variable representations and constraint propagation

Multisets generalize sets by allowing elements to have repetitions. In this paper, we study from a formal perspective representations of multiset variables, and the consistency and propagation of constraints involving multiset variables. These help us model problems more naturally and can, for example, prevent introducing unnecessary symmetries into a model. We identify a number of different representations for multiset variables, compare them in terms of effectiveness and efficiency, and propose inference rules to enforce bounds consistency for the representations. In addition, we propose to exploit the variety of a multiset—the number of distinct elements in it—to improve modeling expressiveness and further enhance constraint propagation. We derive a number of inference rules involving the varieties of multiset variables. The rules interact varieties with the traditional components of multiset variables (such as cardinalities) to obtain stronger propagation. We also demonstrate how to apply the rules to perform variety reasoning on some common multiset constraints. Experimental results show that performing variety reasoning on top of cardinality reasoning can effectively reduce more search space and achieve better runtime in solving some multiset CSPs.     

On generalized communicating P systems with minimal interaction rules

Generalized communicating P systems are purely communicating tissue-like membrane systems with communication rules which allow the movement of only pairs of objects. In this paper, we study the power of these systems in the case of eight restricted variants of communication rules. We show that seven of these restrictions lead to computational completeness, while using the remaining one the systems are able to compute only finite singletons of non-negative integers. The obtained results complete the investigations of the computational power of generalized communicating P systems and provide further examples for simple architectures with simple functioning rules which are as powerful as Turing machines.     

A Generalized Higher-Order Chemical Computation Model

Gamma is a programming model where computation is seen as chemical reactions between data represented as molecules floating in a chemical solution. Formally, this model is represented by the rewriting of a multiset where rewrite rules model the chemical reactions. Recently, we have proposed the γ-calculus, a higher-order extension, where the rewrite rules are first-class citizen. The work presented in this paper increases further the expressivity of the chemical model with generalized multisets: multiplicities of elements may be infinite and/or negative. Applications of these new notions are illustrated by some programming examples.     

Generalized normal form for rewriting P systems

P systems, introduced by Gh. Păun [9] as a new theoretical model for molecular computations, are based on the notion of membrane structure. Several variants of P systems have been proposed and shown to be computationally universal. One of such variant is the rewriting P systems, where we consider string-objects and process them using rewriting rules. Particular cases of normal forms for rewriting P systems were proposed in [11–13]. In this work we introduce the generalized normal form for rewriting P systems which take into consideration the depth of the membrane structure and the number of rewriting rules present in each membrane. Such generalized normal forms are given for rewriting P systems with priorities, and for partially parallel rewriting P systems. In this way, several results from the literature are generalized and improved. Received: 14 March 2002 / 5 June 2002     

Bond computing systems: a biologically inspired and high-level dynamics model for pervasive computing

Targeting at modeling the high-level dynamics of pervasive computing systems, we introduce bond computing systems (BCS) consisting of objects, bonds and rules. Objects are typed but addressless representations of physical or logical (computing and communicating) entities. Bonds are typed multisets of objects. In a BCS, a configuration is specified by a multiset of bonds, called a collection. Rules specify how a collection evolves to a new one. A BCS is a variation of a P system introduced by Gheorghe Paun where, roughly, there is no maximal parallelism but with typed and unbounded number of membranes, and hence, our model is also biologically inspired. In this paper, we focus on regular bond computing systems (RBCS), where bond types are regular, and study their computation power and verification problems. Among other results, we show that the computing power of RBCS lies between linearly bounded automata (LBA) and LBC (a form of bounded multicounter machines) and hence, the regular bond-type reachability problem (given an RBCS, whether there is some initial collection that can reach some collection containing a bond of a given regular type) is undecidable. We also study a restricted model (namely, B-boundedness) of RBCS where the reachability problem becomes decidable.     

Automata and processes on multisets of communicating objects

Inspired by P systems initiated by Gheorghe Pãun, we study a computation model over a multiset of communicating objects. The objects in our model are instances of finite automata. They interact with each other by firing external transitions between two objects. Our model, called a service automaton, is intended to specify, at a high level, a service provided on top of network devices abstracted as communicating objects. We formalize the concept of processes, running over a multiset of objects, of a service automaton and study the computing power of both single-process and multiprocess service automata. In particular, in the multiprocess case, regular maximal parallelism is defined for inter-process synchronization. It turns out that single-process service automata are equivalent to vector addition systems and hence can define nonregular processes. Among other results, we also show that Presburger reachability problem for single-process service automata is decidable, while it becomes undecidable in the multiprocess case. Hence, multiprocess service automata can not be effectively simulated by vector addition systems.     

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

Finite state based testing of P systems

In this paper, we propose an approach to P system testing based on finite state machine conformance techniques. Of the many variants of P systems that have been defined, we consider cell-like P systems which use non-cooperative transformation and communication rules. We show that a (minimal) deterministic finite cover automaton (DFCA) (a finite automaton that accepts all words in a given finite language, but can also accept words that are longer than any word in the language) provides the right approximation for the computation of a P system. Furthermore, we provide a procedure for generating test sets directly from the P system specification (without explicitly constructing the minimal DFCA model).     

P systems with control nuclei: The concept

We describe an extension of P systems where each membrane has an associated control nucleus responsible with the generation of the rules to be applied in that membrane. The nucleus exports a set of rules which are applied in the membrane region (only for one step, but in the usual maximal-parallel way), then the rules are removed and a new iteration of this process takes place. This way, powerful control mechanisms may be included in P systems themselves, as opposed to using the level of “strategies” previously exploited for simulating P systems. The nuclei may contain general programs for generating rules, ranging from those using information on the full system, to more restricted programs where only local information in the nuclei themselves and the associated membranes is used. The latter approach, mixed with a particular mechanism for the representation of the control programs, the rules, and the export procedure is powerful enough for modeling complex biological applications, e.g., to develop a detailed model for cell growth and division in normal and abnormal (tumoral) evolution of biological systems.     

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.     

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.     

(Tissue) P systems working in the k-restricted minimally or maximally parallel transition mode

We investigate variants of the maximally and the minimally parallel transition mode, i.e., we allow only a bounded number of rules to be taken from every set of the partitioning of the whole set of rules. The 1-restricted minimally parallel transition mode especially fits to describe the way transitions take place in spiking neural P systems without delays, i.e., in every neuron where a rule is applicable exactly one rule has to be applied. Moreover, purely catalytic P systems working in the maximally parallel transition mode can be described as P systems using the corresponding rules without catalysts, i.e., noncooperative rules, when working in the 1-restricted minimally parallel transition mode. In contrast to these results for computationally complete models of P systems, with the k-restricted maximally parallel transition mode noncooperative rules only allow for the generation of semi-linear sets.     

A multiset-based model of synchronizing agents: Computability and robustness

We introduce a modelling framework and computational paradigm called Colonies of Synchronizing Agents (CSAs) inspired by the intracellular and intercellular mechanisms in biological tissues. The model is based on a multiset of agents in a common environment. Each agent has a local state stored in the form of a multiset of atomic objects, which is updated by global multiset rewriting rules either independently or synchronously with another agent. We first define the model then study its computational power, considering trade-offs between internal rewriting (intracellular mechanisms) and synchronization between agents (intercellular mechanisms). We also investigate dynamic properties of CSAs, including behavioural robustness (ability to generate a core behaviour despite agent loss or rule failure) and safety of synchronization (ability of an agent to synchronize with some other agent whenever needed).     

A Port Graph Calculus for Autonomic Computing and Invariant Verification

From our previous work on biochemical applications, the structure of port graph (or multigraph with ports) and a rewriting calculus have proved to be well-suited formalisms for modeling interactions between proteins. Then port graphs have been proposed as a formal model for distributed resources and grid infrastructures, where each resource is modeled by a node with ports. The lack of global information and the autonomous and distributed behavior of components are modeled by a multiset of port graphs and rewrite rules which are applied locally, concurrently, and non-deterministically. Some computations take place wherever it is possible and in parallel, while others may be controlled by strategies. In this paper, we first introduce port graphs as graphs with multiple edges and loops, with nodes having explicit connection points, called ports, and edges attaching to ports of nodes. We then define an abstract biochemical calculus that instantiates to a rewrite calculus on these graphs. Rules and strategies are themselves port graphs, i.e. first-class objects of the calculus. As a consequence, they can be rewritten as well, and rules can create new rules, providing a way of modeling adaptive systems. This approach also provides a formal framework to reason about computations and to verify useful properties. We show how structural properties of a modeled system can be expressed as strategies and checked for satisfiability at each step of the computation. This provides a way to ensure invariant properties of a system. This work is a contribution to the formal specification and verification of adaptive systems and to theoretical foundations of autonomic computing.