Search

Nowadays, the success of neural networks as reasoning systems is doubtless. Nonetheless, one of the drawbacks of such reasoning systems is that they work as black-boxes and the acquired knowledge is not human readable. In this paper, we present a new step in order to close the gap between connectionist and logic based reasoning systems. We show that two of the most used inference rules for obtaining negative information in rule based reasoning systems, the so-called Closed World Assumption and Negation as Finite Failure can be characterized by means of spiking neural P systems, a formal model of the third generation of neural networks born in the framework of membrane computing. [ABSTRACT FROM AUTHOR]

Self-reconfigurable robots are built by modules which can move in relationship to each other, which allows the robot to change its physical form. Finding a sequence of module moves that reconfigures the robot from the initial configuration to the goal configuration is a hard task and many control algorithms have been proposed. In this paper, we present a novel method which combines a cluster-flow locomotion based on cellular automata together with a decentralized local representation of the spatial geometry based on membrane computing ideas. This new approach has been tested with computer simulations and real-world experiments performed with modular self-reconfigurable robots and represents a new point of view with respect other control methods found in the literature. [ABSTRACT FROM AUTHOR]

We introduce new possibilities to control the application of rules based on the preceding applications, which can be defined in a general way for (hierarchical) P systems and the main known derivation modes. Computational completeness can be obtained even with non-cooperative rules and using both activation and blocking of rules, especially for the set modes of derivation, when allowing derivation steps with no rules being applied. When we allow the application of rules to influence the application of rules in previous derivation steps, applying a non-conservative semantics for what we consider to be a valid infinite derivation, we can even "go beyond Turing". [ABSTRACT FROM AUTHOR]

Inspiration from nature and especially from biology is up today a multidisciplinary challenge where biologists aim to exploit 'competences' of a computer to understand phenomena of life through simulations and where artificial intelligence aims to develop new computational approaches inherent from natural processes. Situated in the border of evolutionary systems and bioinformatics, the computational model of P system is an evolved algorithm based upon the structure and evolution rules of biological living cells to outperform some conventional systems. Thus, this paper presents a version of multi-compartmental Gillespie algorithm used to simulate the parallelism of chemical reactions in the quorum sensing phenomena of a bacteria colony. This model is used to distribute the computation over the membranes. The aim is to achieve scalability and get mapping the communication between bacteria and their environment. The obtained results prove that this process adds an important value to the multi-compartmental Gillespie algorithm, which uses the organizational aspect of the membrane structure. They also prove that the independent parallel evolution of the membranes is basic to improve legitimacy of the strategy which leads to a reliable simulation and gives a more realistic representation of the system's evolution. [ABSTRACT FROM AUTHOR]

In the framework of Membrane Computing, several tools to tackle the P versus NP problems by means of frontiers of the efficiency expressed in terms of syntactic or semantic ingredients, have been developed. In this paper, an overview of the results in computational complexity theory concerning to membrane systems (tissue-like and cell-like approach) with symport/antiport rules (where objects are transported without evolving), is given. The frontiers are formulated regarding the length of communication rules, the kind of rules implementing the production of an exponential number of cells/membranes in polynomial time, and the role of the environment. An interesting remark of the obtained results refers that the underlying structure to membrane systems (directed graph versus rooted tree) does not matter in this context. [ABSTRACT FROM AUTHOR]

P colonies, tissue-like P systems with very simple components, have received constant attention from the membrane computing community and in the last years several new variants of the model have been considered. Another P system model, namely kernel P system, integrating the most successfully used features of membrane systems, has recently attracted interest and some important developments have been reported. In this paper we study connections among several classes of P colonies and kernel P systems, by showing how the behaviour of these P colony systems can be represented as kernel P systems. An example illustrates the way it is modelled by using P colonies and kernel P systems and some properties of it are formally proved in the latter approach. [ABSTRACT FROM AUTHOR]

In this paper we propose a new graph based P system. The main feature of graph P system is that membrane compartments spread on edges as well as on vertices. These two kinds of compartments are topologically connected with certain communication rules. A new neural computing technique is proposed to solve cluster splitting into finding the equilibrium of Hopfield neural networks. Then we use the new graph P systems to obtain stable status of the neural networks. An example is presented to show the computing efficiency of the new P system with comparison with classical genetic algorithms. [ABSTRACT FROM AUTHOR]

Constrained global optimization is a highly important and challenging task in the field of optimization, and is embedded in many science and engineering optimizations. In this paper, an improved dynamic membrane evolutionary algorithm based on particle swarm optimization and differential evolution (IDMEA-PSO/DE) is proposed to solve constrained engineering design problems. The method combines the dynamic membrane structure of P systems and the PSO/DE search strategy. The performance of IDMEA-PSO/DE is tested on several well-known engineering design problems. The results of the simulation experiments show that the proposed algorithm is effective and outperforms other state-of-the-art-algorithms. [ABSTRACT FROM AUTHOR]

Graph theory is widely used in numerous fields, such as, engineering, physics, social and biological sciences; linguistics etc. The minimum dominating set (MDS) problem is one of the main problems of algorithmic graph theory and has numerous applications especially in graph mining. Since it is NP-hard to solve the MDS problem approximately, much work has been dedicated to central and distributed approximation algorithms for restricted graph classes. In recent research exponential time $$O(k^{n})$$ algorithms are used for some graph classes for solving the MDS problem. In the approach of using the algorithmic tile self-assembly model, the MDS problem has been solved in $$O(n^{2})$$ steps. On the other hand, in the area of membrane computing, P systems introduce two levels of parallelism: every membrane works concurrently with other membranes,and, rules are applied in parallel in each membrane. This paper introduces an algorithm based on the parallelism feature of the P systems model for solving the MDS problem in linear time O( n). [ABSTRACT FROM AUTHOR]

Membrane computing is an emergent research area studying the behavior of living cells to define bio-inspired computing devices, also called P systems. Such devices provide polynomial time solutions to NP-complete problems by trading time for space. The efficient simulation of P systems poses three major challenging issues: an intrinsic massive parallelism of P systems, an exponential computational workspace, and a non-intensive floating point nature. This paper analyzes the simulation of a family of recognizer P systems with active membranes that solves the satisfiability problem in linear time on three different architectures: a shared memory multiprocessor, a distributed memory system, and a manycore graphics processing unit (GPU). For an efficient handling of the exponential workspace created by the P systems computation, we enable different data policies on those architectures to increase memory bandwidth and exploit data locality through tiling. Parallelism inherent to the target P system is also managed on each architecture to demonstrate that GPUs offer a valid alternative for high-performance computing at a considerably lower cost. Our results lead to execution time improvements exceeding 310 $$\times $$ and 78 $$\times $$ , respectively, for a much cheaper high-performance alternative. [ABSTRACT FROM AUTHOR]

In this paper we investigate the operations of insertion and deletion performed at the ends of a string. We show that using these operations in a P systems framework (which corresponds to using specific variants of graph control), computational completeness can even be achieved with the operations of left and right insertion and deletion of only one symbol, both in the generating as well as in the accepting case. [ABSTRACT FROM AUTHOR]

We present GPU implementations of two different nature-inspired optimization methods for well-known optimization problems. Ant Colony Optimization (ACO) is a two-stage population-based method modelled on the foraging behaviour of ants, while P systems provide a high-level computational modelling framework that combines the structure and dynamic aspects of biological systems (in particular, their parallel and non-deterministic nature). Our methods focus on exploiting data parallelism and memory hierarchy to obtain GPU factor gains surpassing 20x for any of the two stages of the ACO algorithm, and 16x for P systems when compared to sequential versions running on a single-threaded high-end CPU. Additionally, we compare performance between GPU generations to validate hardware enhancements introduced by Nvidia's Fermi architecture. [ABSTRACT FROM AUTHOR]

We propose four fast synchronous distributed message-based algorithms, to identify maximum cardinality sets of edge- and node-disjoint paths, between a source node and a target node in a digraph. Previously, Dinneen et al. presented two algorithms, based on the classical distributed depth-first search (DFS), which run in O( mf) steps, where m is the number of edges and f is the number of disjoint paths. Combining Cidon's distributed DFS and our new result, Theorem 3, we propose two improved DFS-based algorithms, which run in O( nf) steps, where n is the number of nodes. We also present improved versions of our two breadth-first search (BFS) based algorithms, with the same complexity upperbound, O( nf). Empirically, for a large set of randomly generated digraphs, our DFS-based edge-disjoint algorithm is 39 % faster than Dinneen et al.'s edge-disjoint algorithm and our BFS-based edge-disjoint algorithm is 80 % faster. All these improved algorithms have been inspired and guided by a P system modelling exercise, but are suitable for any distributed implementation. [ABSTRACT FROM AUTHOR]

In the field of molecular computing, in particular P systems, synchronization is an important requirement for composing or sequentially linking together congenial P system activities. We provide a deterministic algorithm to the Firing Squad Synchronization Problem, for digraph-based P systems, which runs in 3 e + 11 steps, where e is the eccentricity of the general. Our algorithm uses a convenient framework, called simple P modules, which embraces the essential features of several popular types of P systems. [ABSTRACT FROM AUTHOR]

We study reversibility and determinism aspects and the strong versions of these properties of sequential multiset processing systems and of maximally parallel systems, from the computability point of view. In the sequential case, syntactic criteria are established for both strong determinism and strong reversibility. In the parallel case, a criterion is established for strong determinism, whereas strong reversibility is shown to be decidable. In the sequential case, without control all four classes-deterministic, strongly deterministic, reversible, strongly reversible-are not universal, whereas in the parallel case deterministic systems are universal. When allowing inhibitors, the first and the third class become universal in both models, whereas with priorities all of them are universal. In the maximally parallel case, strongly deterministic systems with both promoters and inhibitors are universal. We also present a few more specific results and conjectures. [ABSTRACT FROM AUTHOR]

Membrane Computing is a discipline aiming to abstract formal computing models, called membrane systems or P systems, from the structure and functioning of the living cells as well as from the cooperation of cells in tissues, organs, and other higher order structures. This framework provides polynomial time solutions to NP-complete problems by trading space for time, and whose efficient simulation poses challenges in three different aspects: an intrinsic massively parallelism of P systems, an exponential computational workspace, and a non-intensive floating point nature. In this paper, we analyze the simulation of a family of recognizer P systems with active membranes that solves the Satisfiability problem in linear time on different instances of Graphics Processing Units (GPUs). For an efficient handling of the exponential workspace created by the P systems computation, we enable different data policies to increase memory bandwidth and exploit data locality through tiling and dynamic queues. Parallelism inherent to the target P system is also managed to demonstrate that GPUs offer a valid alternative for high-performance computing at a considerably lower cost. Furthermore, scalability is demonstrated on the way to the largest problem size we were able to run, and considering the new hardware generation from Nvidia, Fermi, for a total speed-up exceeding four orders of magnitude when running our simulations on the Tesla S2050 server. [ABSTRACT FROM AUTHOR]

The hand-made graphical representation of the configuration of a P system becomes a hard task when the number of membranes and objects increases. In this paper we present a new software tool, called JPLANT, for computing and representing the evolution of a P system model with membrane creation. We also present some experiments performed with JPLANT and point out new lines for the research in computer graphics with membrane systems. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This article investigates insertion-deletion systems of small size, where at most two symbols can be used in the description of insertion or deletion rules in a context-free or contextual manner. The basic result shows a characterization by context-free grammars of insertion-deletion systems, which insert or delete one symbol in one symbol left context (systems of size (1, 1, 0; 1, 1, 0)). If context-free insertion or deletion rules are considered (systems of size (2, 0, 0; 1, 1, 0) or (1, 1, 0; 2, 0, 0)), then we show that corresponding systems are not computationally complete. However, if the insertion and the deletion operations having same size as above are considered in the distributed framework of P systems, then the computational power strictly increases and the obtained models become computationally complete. The article also shows that if context-free insertion and deletion rules of two symbols (of size (2, 0, 0; 2, 0, 0)) are used in combination with P systems, then the obtained model is still not computationally complete. Finally some open problems are presented. [ABSTRACT FROM AUTHOR]

We present Spatial P systems, a variant of P systems which embodies the concept of space and position inside a membrane. Objects in membranes are associated with positions. Rules specify, in the usual way, the objects which are consumed and the ones which are produced; in addition, they can specify the positions of the produced objects. Objects belong to two different sets: the set of ordinary objects and the set of mutually exclusive objects. Every position inside a membrane can accommodate an arbitrary number of ordinary objects, but at most one mutually exclusive object. We prove that Spatial P systems are universal even if only non-cooperating rules are allowed. We also show how Spatial P systems can be used to model the evolution of populations in presence of geographical separations. [ABSTRACT FROM AUTHOR]

This paper presents two approaches based on metabolic and stochastic P systems, together with their associated analysis methods, for modelling biological systems and illustrates their use through two case studies. [ABSTRACT FROM AUTHOR]

In this work we give a formalization of Hybrid Functional Petri Nets, shortly HFPN, an extension of Petri Nets for biopathways modelling, and we compare them with Metabolic P Systems. An introduction to both the formalisms is given, together with highlights about respective similarities and differences. Their equivalence is thus proved by means of a theorem which holds under quite general hypotheses. The case study of the lac operon gene regulatory mechanism in the glycolytic pathway of Escherichia coli is modeled by an MP system which provides the same dynamics of an equivalent HFPN model. [ABSTRACT FROM AUTHOR]

This paper proposes a new methodology for the automated design of cell models for systems and synthetic biology. Our modelling framework is based on P systems, a discrete, stochastic and modular formal modelling language. The automated design of biological models comprising the optimization of the model structure and its stochastic kinetic constants is performed using an evolutionary algorithm. The evolutionary algorithm evolves model structures by combining different modules taken from a predefined module library and then it fine-tunes the associated stochastic kinetic constants. We investigate four alternative objective functions for the fitness calculation within the evolutionary algorithm: (1) equally weighted sum method, (2) normalization method, (3) randomly weighted sum method, and (4) equally weighted product method. The effectiveness of the methodology is tested on four case studies of increasing complexity including negative and positive autoregulation as well as two gene networks implementing a pulse generator and a bandwidth detector. We provide a systematic analysis of the evolutionary algorithm’s results as well as of the resulting evolved cell models. [ABSTRACT FROM AUTHOR]

The distributed implementation of P systems on a cluster of processors has met with a bottleneck communications problem. When the number of membranes grows in the system, the network gets congested and the time taken to execute an evolution step degrades. In this article, we suggest a software architecture denominated “partially parallel evolution with partially parallel communication”, where some membranes are located in each processor, proxies are used to communicate with membranes located in different processors, and a policy of access control to the communications network is mandatory. With all this, we get a certain parallelism in the system and an acceptable functioning in communications. In addition to this, it establishes a series of equations that allows us to determine in the architecture the optimum number of processors needed, the time required to execute an evolution step, the number of membranes to be located in each processor, and the conditions to determine when it is best to use the distributed solution or the sequential one. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]