nach oben

2012 | Buch

Kapitel lesen Erstes Kapitel lesen

Membrane Computing

12th International Conference, CMC 2011, Fontainebleau, France, August 23-26, 2011, Revised Selected Papers

herausgegeben von: Marian Gheorghe, Gheorghe Păun, Grzegorz Rozenberg, Arto Salomaa, Sergey Verlan

Verlag: Springer Berlin Heidelberg

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 12th International Conference on Membrane Computing, CMC 2011, held in Fontainebleau, France, in August 2011. The 19 revised selected papers presented were carefully reviewed and selected from 27 papers and 5 posters presented at the conference. The book also contains full papers or extended abstracts of the 5 invited presentations. The papers address all the main directions of research in membrane computing, ranging from theoretical topics in the mathematics and computer science to application issues.

Inhaltsverzeichnis

Frontmatter

Invited Presentations

Properties of Membrane Systems

Abstract

The goal of this survey is to overview some important properties of membrane systems that are referred to as “promising” or dynamic. It is sometimes quite desirable to achieve them, although they are mostly undecidable. We summarize how some of these properties affect the computational power or the descriptional complexity of membrane systems. A number of variants of the dynamic systems is also discussed. Finally, a few self-stabilization properties are proposed.

Artiom Alhazov

Bridging Biology and Engineering Together with Spatial Computing

Abstract

Biological systems can often be viewed as spatial computers: space-filling collections of computational devices with strongly localized communication. Applying a continuous-space abstraction allows the behavior of such systems to be modeled or specified in terms of aggregate geometry and information flow. This can simplify both the engineering of biological systems and the application of biological models to the engineering of non-biological systems, as illustrated by examples from synthetic biology and morphogenetic engineering.

Jacob Beal

The Modeling and the Simulation of the Fluid Machines of Synthetic Biology

Abstract

In the past century, several conceptual and technological breakthroughs produced the digital computers and open the digital information age. At the very same time, the Watson – Crick model of the digital coding of the genetic information was developed. Despite this parallel development, biology as long focused in the understanding of existing systems shaped by natural evolution whilst computer science has built its own (hardware and software) objects from scratch.

This situation is no longer true: the emergence of synthetic biology opens the doors to the systematic design and construction of biological (fluid) machines. However, even if fluid machines can be based on a kind of digital information processing, they differ from the discrete dynamical systems we are used in computer science: they have a dynamical structure.

In this paper, we stress the parallel between the development of digital information processing and genetic information processing. We sketch some tools developed or appropriated in computer science that can be used to model and specify such fluid machines. We show through an example the use of mgs, a domain specific language, in the proof of concept of a “multicellular bacterium” designed at the 2007 iGEM competition.

Jean-Louis Giavitto

Parallel and Distributed Algorithms in P Systems

Abstract

Our group’s recent quest has been to use P systems to model parallel and distributed algorithms. Several framework extensions are recalled or detailed, in particular, modular composition with information hiding, complex symbols, generic rules, reified cell IDs, asynchronous operational modes, asynchronous complexity. We motivate our proposals via P system models of several well-known distributed algorithms, such as leader election and distributed echo. As another type of application, we mention a dynamic programming algorithm for stereo matching in image processing. We suggest criteria to assess the merits of this modelling approach and offer preliminary evaluations of our proposed additional ingredients, which have been useful in refactoring existing systems and could be useful to the larger P systems community.

Radu Nicolescu

Variants of Distributed P Automata and the Efficient Parallelizability of Languages

Abstract

We give an overview of P automata and distributed P automata and the parallelizability of their accepted languages by focusing on those features of these systems which influence the efficiency of the parallelization.

György Vaszil

Regular Presentations

Quantitative Causality in Membrane Systems

Abstract

We define and study specific and general causality in terms of multisets of objects and of multisets of rules. We relate the two notions of causality, and provide characterizations for each of them. We give an inductive method of obtaining the general causes of a multiset of objects, and use the general causes of a multiset v to find all the multisets u from which v can be obtained in a single evolution step.

Oana Agrigoroaiei, Gabriel Ciobanu

Circular Post Machines and P Systems with Exo-insertion and Deletion

Abstract

This paper focuses on P systems with one-symbol insertion and deletion without contexts. The main aim of this paper is to consider the operations applied at the ends of the string, and prove the computational completeness in case of priority of deletion over insertion. This result presents interest since the strings are controlled by a tree structure only, and because insertion and deletion of one symbol are the simplest string operations.

To obtain a simple proof, we introduce here a new variant (CPM5) of circular Post machines (Turing machines moving one-way on a circular tape): those with instructions changing a state and either reading one symbol or writing one symbol. We believe CPM5 deserves attention as a simple, yet useful tool.

In the last part of the paper, we return to the case without priorities. We give a lower bound on the power of such systems, which holds even for one-sided operations only.

Artiom Alhazov, Alexander Krassovitskiy, Yurii Rogozhin

A Spiking Neural P System Simulator Based on CUDA

Abstract

In this paper we present a Spiking Neural P system (SNP system) simulator based on graphics processing units (GPUs). In particular we implement the simulator using NVIDIA CUDA enabled GPUs. The massively parallel architecture of current GPUs is very suitable for the maximally parallel computations of SNP systems. We simulate a wider variety of SNP systems, after presenting a previous work on SNP system matrix representation which led to their simulation in GPUs, and the simulation algorithm included here. Finally, we compare and present the performance speedups of the CPU-GPU based simulator over the CPU only simulator.

Francis George C. Cabarle, Henry Adorna, Miguel A. Martínez

Modularity in P Colonies with Checking Rules

Abstract

P colony, which was introduced in [9], is an abstract computing device composed of independent agents, acting and evolving in a shared environment. In this paper we bring a new view to investigation of the behavior of the P colonies. The first part of the paper focuses on the modularity of the P colonies with checking rules. We group the agents into modules with specific function. In the second part of the paper we introduce improved results concerning the computational power of the P colonies with capacity one.

Luděk Cienciala, Lucie Ciencialová, Miroslav Langer

Finite dP Automata versus Multi-head Finite Automata

Abstract

We describe a connection between dP automata (distributed P automata) and non-deterministic multi-head finite automata. We introduce the concepts of agreement languages of dP automata, and the notion of a two-way dP automaton. We demonstrate how the languages of non-deterministic one-way and two-way multi-head finite automata can be obtained as the agreement languages of one-way and two-way finite dP automata.

Erzsébet Csuhaj-Varjú, György Vaszil

An Adaptive Algorithm for P System Synchronization

Abstract

We present an improved solution for the Firing Squad Synchronization Problem (FSSP) for digraph-structured P systems. We improve our previous FSSP algorithm by allowing the general to delegate a more central cell in the P system to send the final command to synchronize. With e being the eccentricity of the general and r denoting the radius of the underlying digraph, our new algorithm guarantees to synchronize all cells of the system, between e + 2r + 3 steps (for all trees structures and many digraphs) and up to 3e + 7 steps, in the worst case for any digraph. Empirical results show our new algorithm for tree-structured P systems yields at least 20% reduction in the number of steps needed to synchronize over the previous best-known algorithm.

Michael J. Dinneen, Yun-Bum Kim, Radu Nicolescu

P Systems with Active Membranes Operating under Minimal Parallelism

Abstract

We prove that P systems with active membranes operating under minimal parallelism are able to solve NP-complete and PP-complete problems in linear time and exponential space when using different types of rules. We also prove that these systems can simulate register machines.

Pierluigi Frisco, Gordon Govan

Chemical Analog Computers for Clock Frequency Control Based on P Modules

Abstract

Living organisms comprise astonishing capabilities of information processing for efficient adaptation to environmental changes. Resulting chemical control loops and regulator circuits are expected to exhibit a high functional similarity to technical counterparts subsumed by analog computers. A fascinating example is given by circadian clocks providing an endogenous biological rhythm adapted to the daily variation of sunlight and darkness. Its underlying biochemical principle of operation suggests a general functional scheme corresponding to frequency control using phase-locked loops (PLL). From a systems biology point of view, clock systems can be decomposed into specific modules like low-pass filters, arithmetic signal comparators, and controllable core oscillators. Each of them processes analog chemical signals on the fly. We introduce P modules in order to capture structure, behaviour, and interface of pure chemical analog computer models in terms of building blocks along with two simulation case studies. The first one is focused on chemical analog computer components including a controllable Goodwin-type core oscillator while the second one evolves an entire PLL-based frequency control by means of a pure chemical circadian clock model.

Thomas Hinze, Christian Bodenstein, Benedict Schau, Ines Heiland, Stefan Schuster

Evolutionary Design of a Simple Membrane System

Abstract

The programmability of membrane systems is an ongoing and challenging issue. This paper focuses on the automatic design of a simple membrane system for fulfilling a specific task by using a quantum-inspired evolutionary algorithm and the P-lingua simulator. The design consists of the pre-defined membrane structure and initial objects, a set of possible evolution rules, the coding technique of membrane systems, evolutionary operators and a fitness function for evaluating different membrane systems. Experiments conducted on P-lingua simulator show that the presented design approach is feasible and effective to automatically evolve a membrane system for solving some specific tasks. The results also show that a quantum-inspired evolutionary algorithm is more appropriate than a genetic algorithm, recently reported in the literature, for designing a membrane system.

Xiaoli Huang, Gexiang Zhang, Haina Rong, Florentin Ipate

Formal Verification of P Systems with Active Membranes through Model Checking

Abstract

Formal verification of P systems using model checking has attracted a significant amount of research in recent years. However, up to now only P systems with static structure have been considered. This paper makes significant advances in this area by considering P systems with active membranes, in particular P systems with division rules. The paper presents a theoretical framework for addressing this problem and reports on a complex case study involving a well-known NP-complete problem solved using P systems with membrane division rules. This is implemented in Promela and non trivial properties are verified using Spin.

Florentin Ipate, Raluca Lefticaru, Ignacio Pérez-Hurtado, Mario J. Pérez-Jiménez, Cristina Tudose

Basic Concurrency Resolution in Clock-Free P Systems

Abstract

Clock-free P systems are an almost completely asynchronous model of P systems in which each rule application lasts for a different time. This makes the processes in this model more similar to the chemical processes in the biological cell, but also poses similar design problems as in concurrent programming. In this paper an attempt is made to solve synchronisation problems in clock-free P systems using the approaches commonly used in concurrent programming.

Sergiu Ivanov

Asynchronous Extended Spiking Neural P Systems with Astrocytes

Abstract

A variant of spiking neural P systems was recently investigated by the authors, using astrocytes that have excitatory and inhibitory influence on synapses. In this work, we consider this system in the non-synchronized (i.e., asynchronous) mode: in any step, when a neuron is enabled, it is not obligatorily fired, making a global clock dispensable. It is proved that asynchronous spiking neural P systems with astrocytes are universal (when using extended rules). The construction is uniform in the sense that the form of the modules used is independent of the simulated register machine.

Linqiang Pan, Jun Wang, Hendrik Jan Hoogeboom

A P–Lingua Based Simulator for Spiking Neural P Systems

Abstract

The research within the field of Spiking Neural P systems (SN P systems, for short) is focusing mainly in the study of the computational completeness (they are equivalent in power to Turing machines) and computational efficiency of this kind of systems. These devices have been shown capable of providing polynomial time solutions to computationally hard problems by making use of an exponential workspace constructed in a natural way. In order to experimentally explore this computational power, it is necessary to develop software that provides simulation tools (simulators) for the existing variety of SN P systems. Such simulators allow us to carry out computations of solutions to NP-complete problems on certain instances. Within this trend, P-Lingua provides a standard language for the definition of P systems. As part of the same project, pLinguaCore library provides particular implementations of parsers and simulators for the models specified in P-Lingua. In this paper, an extension of the P-Lingua language to define SN P systems is presented, along with an upgrade of pLinguaCore including a parser and a new simulator for the variants of these systems included in the language.

Luis F. Macías–Ramos, Ignacio Pérez–Hurtado, Manuel García–Quismondo, Luis Valencia–Cabrera, Mario J. Pérez–Jiménez, Agustín Riscos–Núñez

Computing with Multi-membranes

Abstract

Multi-Membranes are introduced for defining a computation model inspired to Metabolic P systems. It is a deterministic, distributed, and computationally universal model, where computations are performed by transferring objects among membranes with fluxes specified by membrane contents. Arithmetical functions can be naturally described and, remarkably, the algorithms can be described by means of pure geometrical forms without any textual information.

Vincenzo Manca, Rosario Lombardo

A Methodology Based on MP Theory for Gene Expression Analysis

Abstract

In this paper we develop an application of the MP theory to gene expression analysis. After introducing some general concepts about transcriptome analysis and about gene networks, we delineate a methodology for modelling such kind of networks by means of Metabolic P systems. MP systems were initially introduced as models of metabolic processes, but they can be successfully used in each context where we want to infer models of a system from a given set of time series. In the case of gene expression analysis, we found a standard way for translating MP grammars involving gene expressions into corresponding quantitative gene networks. Pre-processing methods of raw time series have been also elaborated in order to achieve a successful MP modelling of the underlying gene network.

Luca Marchetti, Vincenzo Manca

Generalized Gandy-Păun-Rozenberg Machines for Tile Systems and Cellular Automata

Abstract

A concept of a generalized Gandy-Păun-Rozenberg machine for modelling various systems of multidimensional tile-like compartments with common parts (tile faces) of compartment boundaries by graph rewriting is introduced, where some massive parallelism of computations or evolution processes generated by these systems is respected. The representation of Gandy–Păun–Rozenberg machines by Gandy machines in [16] is extended to the case of generalized Gandy–Păn–Rozenberg machines, where the machines represented by Gandy machines are equivalent to Turing machines.

Adam Obtułowicz

Sequentiality Induced by Spike Number in SNP Systems: Small Universal Machines

Abstract

In this paper we consider sequential SNP systems where the sequentiality of the system is induced by the max-spike: the neuron with the maximum number of spikes out of the neurons that can spike at one step will fire. This corresponds to a global view of the whole network that makes the system sequential. We continue the study in the direction of max-spike and show that systems with 132 neurons are universal. This improves a recent result in the area.

Andrei Păun, Manuela Sidoroff

P Systems Simulating Oracle Computations

Abstract

We show how existing P systems with active membranes can be used as modules inside a larger P system; this allows us to simulate subroutines or oracles. As an application of this construction, which is (in principle) quite general, we provide a new, improved lower bound to the complexity class PMC \(_{\mathcal{AM}(-{\rm d},-{\rm n})}\) of problems solved by polynomial-time P systems with (restricted) elementary active membranes: this class is proved to contain P ^PP and hence, by Toda’s theorem, the whole polynomial hierarchy.

Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron

P Systems with Chained Rules

Abstract

In this paper we introduce a new model of P systems that uses vectors of rules to describe a causal dependence relation between the executions of the rules. We also study their computational power by considering several restrictions on the types of the rules.

Dragoş Sburlan

Backmatter

Titel: Membrane Computing
herausgegeben von: Marian Gheorghe
Gheorghe Păun
Grzegorz Rozenberg
Arto Salomaa
Sergey Verlan
Verlag: Springer Berlin Heidelberg
Electronic ISBN: 978-3-642-28024-5
Print ISBN: 978-3-642-28023-8
DOI: https://doi.org/10.1007/978-3-642-28024-5