Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

Invited Presentations

P Automata: Concepts, Results, and New Aspects

In this paper we discuss P automata, constructs combining properties of classical automata and P systems being in interaction with their environments. We describe the most important variants and their properties, and propose new topics and open problems for future research.

Erzsébet Csuhaj-Varjú

Computational Nature of Processes Induced by Biochemical Reactions

Natural computing is concerned with human-designed computing inspired by nature as well as with computations taking place in nature, i.e., it investigates phenomena taking place in nature in terms of information processing.

Well-known examples of the first strand of research are evolutionary computing, neural computation, cellular automata, swarm intelligence, molecular computing, quantum computation, artificial immune systems, and membrane computing.

Andrzej Ehrenfeucht, Grzegorz Rozenberg

Transition and Halting Modes in (Tissue) P Systems

A variety of different transition modes for (tissue) P systems as well as several halting modes currently are used in the area of membrane computing. In this paper, the definitions of the most important transition modes and halting modes are explained based on networks of cells, a general model for tissue P systems. Moreover, some results for specific variants of (tissue) P systems working on multisets of objects are recalled.

Rudolf Freund

Conformon P Systems and Topology of Information Flow

We survey some of the results about conformon P systems and link these results to the topology of information flow. This topology is studied with models of Petri nets. Several directions of research and open problems are given.

Pierluigi Frisco

Formal Verification and Testing Based on P Systems

In this paper it is surveyed the set of formal verification methods and testing approaches used so far for applications based on P systems.

Marian Gheorghe, Florentin Ipate, Ciprian Dragomir

A Look Back at Some Early Results in Membrane Computing

On this tenth anniversary of the Workshop on Membrane Computing, it seems appropriate and fitting to look back at some early basic contributions in the area. We give a brief summary of results, some of which answered fundamental open questions in the field. These concern complexity issues such as universality versus non-universality, determinism versus nondeterminism, various notions of parallelism, membrane and alphabet-size hierarchies, and characterizations of some classes of P systems.

Oscar H. Ibarra

From P to MP Systems

Metabolic P systems (MP systems) represent metabolic processes in a discrete mathematical framework based on P systems. MP systems are presented, with a special emphasis to their roots and to their relationship with P systems, which provided the right conceptual framework for their development. A synthetic algebraic formulation of MP system is given, and the log-gain theory of MP systems is outlined, by discussing the research perspectives and the methodological aspects of this approach.

Vincenzo Manca

The Biological Cell in Spectacle

It seems that, for some hot topics, the today means aiming to monitor and to survey the published literature in the respective fields are no longer able to accomplish their task. One of these topics is the biological cell.

Obviously, for biology the aim to investigate its functioning is for long time a basic task. It happens, however, that beginning with the middle of the past century, a lot of other disciplines became interested in the problems raised by the biological cell: physics, linguistics, mathematics, computer science, semiotics, philosophy, sociology are only some of them. Having the opportunity to attend some of their meetings and to read some of the respective papers, I was struck by the fact that, despite their different profile, they all start with statements like this: “Our aim is to understand the functioning of the biological cell”. But in their next steps you hardly recognize that they have a common aim. Each of them adopts a specific terminology, a specific jargon, and has specific bibliographic references; moreover, to a large extent, each of them has its specific journals. Under these conditions, you expect that these different directions of research need to interact, but these expectations are not satisfied. They almost ignore each other.

It is scandalous! It is incredible that this may happen! It is a symptom of a grave disease of human communication. I call it a spectacle, but it is rather a spectacle belonging to the absurd; maybe we should describe it as a mixture of absurd and schizophrenia.

In the following, I will sketch some of these directions of research.

Solomon Marcus

Energy-Based Models of P Systems

Energy plays an important role in many theoretical computational models. In this paper we review some results we have obtained in the last few years concerning the computational power of two variants of P systems that manipulate energy while performing their computations: energy-based and UREM P systems. In the former, a fixed amount of energy is associated to each object, and the rules transform objects by manipulating their energy. We show that if we assign local priorities to the rules, then energy–based P systems are as powerful as Turing machines, otherwise they can be simulated by vector addition systems and hence are not universal. We also discuss the simulation of conservative and reversible circuits of Fredkin gates by means of (self)–reversible energy–based P systems. On the other side, UREM P systems are membrane systems in which a given amount of energy is associated to each membrane. The rules transform and move single objects among the regions. When an object crosses a membrane, it may modify the associated energy value. Also in this case, we show that UREM P systems reach the power of Turing machines if we assign a sort of local priorities to the rules, whereas without priorities they characterize the class

PsMAT

λ

, and hence are not universal.

Giancarlo Mauri, Alberto Leporati, Claudio Zandron

A Computational Complexity Theory in Membrane Computing

In this paper, a computational complexity theory within the framework of Membrane Computing is introduced. Polynomial complexity classes associated with different models of cell-like and tissue-like membrane systems are defined and the most relevant results obtained so far are presented. Many attractive characterizations of

P

NP

conjecture within the framework of a bio-inspired and non-conventional computing model are deduced.

Mario J. Pérez–Jiménez

Regular Presentations

Evolving by Maximizing the Number of Rules: Complexity Study

This paper presents the complexity of finding a multiset of rules in a P system in such a way to have a maximal number of rules applied. It is proved that the decision version of this problem is

NP

-complete. We study a number of subproblems obtained by considering that a rule can be applied at most once, and by considering the number of objects in the alphabet of the membrane as being fixed. When considering P systems with simple rules, the corresponding decision problem is in

P

. When considering P systems having only two types of objects, and P systems in which a rule is applied at most once, their corresponding decision problems are

NP

-complete. We compare these results with those obtained for

maxO

evolution.

Oana Agrigoroaiei, Gabriel Ciobanu, Andreas Resios

On Reversibility and Determinism in P Systems

Membrane computing is a formal framework of distributed parallel computing. In this paper we study the reversibility and maximal parallelism of P systems from the computability point of view. The notions of reversible and strongly reversible systems are considered. The universality is shown for reversible P systems with either priorities or inhibitors, and a negative conjecture is stated for reversible P systems without such control. Strongly reversible P systems without control have shown to only generate sub-finite sets of numbers; this limitation does not hold if inhibitors are used.

Another concept considered is strong determinism, which is a syntactic property, as opposed to the determinism typically considered in membrane computing. Strongly deterministic P systems without control only accept sub-regular sets of numbers, while systems with promoters and inhibitors are universal.

Artiom Alhazov, Kenichi Morita

Typed Membrane Systems

We introduce and study typing rules and a type inference algorithm for membrane systems with symport/antiport evolution rules. The main results are given by a subject reduction theorem and the completeness of type inference. We exemplify how the type system is working by presenting a typed description of the sodium-potassium pump.

Bogdan Aman, Gabriel Ciobanu

A P System Based Model of an Ecosystem of Some Scavenger Birds

In [1], we presented a P system in order to study the evolution of the bearded vulture in the Pyrenees (NE Spain). Here, we present a new model that overcomes some limitations of the previous work incorporating other scavenger species and additional prey species that provide food for the scavenger intraguild and interact with the Bearded Vulture in the ecosystem. After the validation, the new model can be a useful tool for the study of the evolution and management of the ecosystem. P systems provide a high level computational modelling framework which integrates the structural and dynamical aspects of ecosystems in a compressive and relevant way. The inherent randomness and uncertainty in ecosystems is captured by using probabilistic strategies.

Mónica Cardona, M. Angels Colomer, Antoni Margalida, Ignacio Pérez-Hurtado, Mario J. Pérez-Jiménez, Delfí Sanuy

Metabolic P System Flux Regulation by Artificial Neural Networks

Metabolic P systems are an extension of P systems employed for modeling biochemical systems in a discrete and deterministic perspective. The generation of MP models from observed data of biochemical system dynamics is a hard problem which requires to solve several subproblems. Among them, flux tuners discovery aims to identify substances and parameters involved in tuning each reaction flux. In this paper we propose a new technique for discovering flux tuners by means of neural networks. This methodology, based on backpropagation with weight elimination for neural network training and on an heuristic algorithm for computing tuning indexes, has achieved encouraging results in a synthetic case study.

Alberto Castellini, Vincenzo Manca, Yasuhiro Suzuki

A Novel Variant of P Systems for the Modelling and Simulation of Biochemical Systems

In the last decade, different computing paradigms and modelling frameworks for the description and simulation of biochemical systems have been proposed. Here, we consider membrane systems, in particular, tissue P systems and

τ

-DPP, for the development of a novel variant of membrane systems with sizes associated to the volumes involved in the structure and to the molecular species occurring inside the system. Moreover, this variant allows the communication of objects among non adjacent membranes arranged in a hybrid structure, that is, organised in a tissue-like fashion where nodes can have a complex internal structure. The features presented in the new variant of P systems can be used to describe, among others, reaction-diffusion systems, where molecules are involved both in chemical reactions and diffusive processes, and their movements depend on the free space of the volumes; or systems where exist privileged pathways between membranes, which are inspired by the role of microtubule in protein transport within the intracellular space.

Paolo Cazzaniga, Giancarlo Mauri, Luciano Milanesi, Ettore Mosca, Dario Pescini

Implementing P Systems Parallelism by Means of GPUs

Software development for Membrane Computing is growing up yielding new applications. Nowadays, the efficiency of P systems simulators have become a critical point when working with instances of large size. The newest generation of GPUs (Graphics Processing Units) provide a massively parallel framework to compute general purpose computations. We present GPUs as an alternative to obtain better performance in the simulation of P systems and we illustrate it by giving a solution to the N-Queens problem as an example.

Jose M. Cecilia, José M. García, Ginés D. Guerrero, Miguel A. Martínez–del–Amor, Ignacio Pérez–Hurtado, Mario J. Pérez–Jiménez

Regulation and Covering Problems in MP Systems

The study of efficient methods to deduce fluxes of biological reactions, by starting from experimental data, is necessary to understand metabolic dynamics, and is a central issue in systems biology. In this paper we report some initial results, together with related open problems, regarding the efficient computation of regulation fluxes in metabolic P systems. By means of Log-gain theory the system dynamics can be linearized, in such a way to be described by a recurrence equations system, of which we point out a few algebraic properties, involving covering problems.

Giuditta Franco, Vincenzo Manca, Roberto Pagliarini

(Tissue) P Systems with Hybrid Transition Modes

In addition to the maximally parallel transition mode used from the beginning in the area of membrane computing, many other transition modes for (tissue) P systems have been investigated since then. In this paper we consider (tissue) P systems with hybrid transition modes where each set of a covering of the whole set of rules may work in a different transition mode in a first level and all partitions of rules work together at a (second) level of the whole system on the current configuration in a maximally parallel way. With all partitions of noncooperative rules working in the maximally parallel mode, we obtain a characterization of Parikh sets of ET0L-languages, whereas with hybrid systems with the partitions either working in the maximally parallel and in the = 1-mode or with all partitions working in the = 1-mode we can simulate catalytic or purely catalytic P systems, respectively, thus obtaining computational completeness.

Rudolf Freund, Marian Kogler

An Overview of P-Lingua 2.0

P–Lingua is a programming language for membrane computing which aims to be a standard to define P systems. In order to implement this idea, a Java library called pLinguaCore has been developed as a software framework for cell–like P systems. It is able to handle input files (either in XML or in P–Lingua format) defining P systems from a number of different cell–like P system models. Moreover, the library includes several built–in simulators for each supported model. For the sake of software portability, pLinguaCore can export a P system definition to any convenient output format (currently XML and binary formats are available). This software is not a closed product, but it can be extended to accept new input or output formats and also new models or simulators.

The term P–Lingua 2.0 refers to the software package consisting of the above mentioned library together with a user interface called pLinguaPlugin (more details can be found at http://www.p-lingua.org).

Finally, in order to illustrate the software, this paper includes an application using pLinguaCore for describing and simulating ecosystems by means of P systems.

Manuel García-Quismondo, Rosa Gutiérrez-Escudero, Ignacio Pérez-Hurtado, Mario J. Pérez-Jiménez, Agustín Riscos-Núñez

Characterizing Tractability by Tissue-Like P Systems

In the framework of recognizer cell–like membrane systems it is well known that the construction of exponential number of objects in polynomial time is not enough to efficiently solve

NP

–complete problems. Nonetheless, it may be sufficient to create an exponential number of membranes in polynomial time.

In this paper, we study the computational efficiency of recognizer tissue P systems with communication (symport/antiport) rules and division rules. Some results have been already obtained in this direction: (a) using communication rules and making no use of division rules, only tractable problems can be efficiently solved; (b) using communication rules with length three and division rules,

NP

–complete problems can be efficiently solved. In this paper, we show that the length of communication rules plays a relevant role from the efficiency point of view for this kind of P systems.

Rosa Gutiérrez–Escudero, Mario J. Pérez–Jiménez, Miquel Rius–Font

Searching Previous Configurations in Membrane Computing

Searching all the configurations

C

′ which produce a given configuration

C

is an extremely hard task. The current approximations are based on heavy hand-made calculus by considering the specific features of the given configuration. In this paper we present a general method for characterizing all the configurations

C

′ which produce a given configuration

C

in the framework of transition P systems without cooperation and without dissolution.

Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez

Modelling Signalling Networks with Incomplete Information about Protein Activation States: A P System Framework of the KaiABC Oscillator

Reconstruction of signal transduction network models based on incomplete information about network structure and dynamical behaviour is a major challenge in current systems biology. In particular, interactions within signalling networks are frequently characterised by partially unknown protein phosphorylation and dephosphorylation cascades at a submolecular description level. For prediction of promising network candidates, reverse engineering techniques typically enumerate the reaction search space. Considering an underlying amount of phosphorylation sites, this implies a potentially exponential number of individual reactions in conjunction with corresponding protein activation states. To manage the computational complexity, we extend P systems with string-objects by a subclass for protein representation able to process wild-carded together with specific information about protein binding domains and their ligands. This variety of reactants works together with assigned term-rewriting mechanisms derived from discretised reaction kinetics. We exemplify the descriptional capability and flexibility of the framework by discussing model candidates for the circadian clock formed by the KaiABC oscillator found in the cyanobacterium

Synechococcus elongatus

. A simulation study of its dynamical behaviour demonstrates effects of superpositioned protein abundance courses based on regular expressions corresponding to dedicated protein activation states.

Thomas Hinze, Thorsten Lenser, Gabi Escuela, Ines Heiland, Stefan Schuster

Solving NP-Complete Problems by Spiking Neural P Systems with Budding Rules

Inspired by the growth of dendritic trees in biological neurons, we introduce spiking neural P systems with budding rules. By applying these rules in a maximally parallel way, a spiking neural P system can exponentially increase the size of its synapse graph in a polynomial number of computation steps. Such a possibility can be exploited to efficiently solve computationally difficult problems in deterministic polynomial time, as it is shown in this paper for the

NP

-complete decision problem

sat

.

Tseren-Onolt Ishdorj, Alberto Leporati, Linqiang Pan, Jun Wang

Tuning P Systems for Solving the Broadcasting Problem

P systems are employed in various contexts to specify or model different problems. In certain cases the system is not entirely known. In this paper we will consider the broadcasting algorithm and present a method to determine the format of the rules of the P system used to specify the algorithm.

Raluca Lefticaru, Florentin Ipate, Marian Gheorghe, Gexiang Zhang

An Improved Membrane Algorithm for Solving Time-Frequency Atom Decomposition

To decrease the computational complexity and improve the search capability of quantum-inspired evolutionary algorithm based on P systems (QEPS), a real-observation QEPS (RQEPS) was proposed. RQEPS is a hybrid algorithm combining the framework and evolution rules of P systems with active membranes and real-observation quantum-inspired evolutionary algorithm (QEA). The RQEPS involves a dynamic structure including membrane fusion and division. The membrane fusion is helpful to enhance the information communication among individuals and the membrane division is beneficial to reduce the computational complexity. An

NP

-complete problem, the time-frequency atom decomposition of noised radar emitter signals, is employed to test the effectiveness and practical capabilities of the RQEPS. The experimental results show that RQEPS is superior to QEPS, the greedy algorithm and binary-observation QEA in terms of search capability and computational complexity.

Chunxiu Liu, Gexiang Zhang, Hongwen Liu, Marian Gheorghe, Florentin Ipate

A Region-Oriented Hardware Implementation for Membrane Computing Applications

We have recently developed a prototype hardware implementation of membrane computing based on reconfigurable computing technology called Reconfig-P. The existing hardware design treats reaction rules as the primary computational entities and represents regions only implicitly. In this paper, we describe and evaluate an alternative hardware design that more directly reflects the intuitive conceptual understanding of a P system and therefore promotes the extensibility of Reconfig-P. A key feature of the design is the fact that regions, rather than reaction rules, are the primary computational entities. More specifically, in the design, regions are represented as loosely coupled processing units which communicate objects by message passing. Experimental results show that for many P systems the region-oriented and rule-oriented designs exhibit similar performance and hardware resource consumption.

Van Nguyen, David Kearney, Gianpaolo Gioiosa

Discovering the Membrane Topology of Hyperdag P Systems

In an earlier paper, we presented an extension to the families of P systems, called hyperdag P systems (hP systems), by proposing a new underlying topological structure based on the hierarchical dag structure (instead of trees or digraphs). In this paper, we develop building-block membrane algorithms for discovery of the global topological structure from the local cell point of view. In doing so, we propose more convenient operational modes and transfer modes, that depend only on each of the individual cell rules.

Finally, by extending our initial work on the visualization of hP system membranes with interconnections based on dag structures without transitive arcs, we propose several ways to represent structural relationships, that may include transitive arcs, by simple-closed planar regions, which are folded (and possibly twisted) in three dimensional space.

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

A Note on Small Universal Spiking Neural P Systems

In the “standard” way of simulating register machines by spiking neural P systems (in short, SN P systems), one neuron is associated with each instruction of the register machine that we want to simulate. In this note, a new way is introduced for simulating register machines by SN P systems, where only one neuron is used for all instructions of a register machine; in this way, we can use less neurons to construct universal SN P systems. Specifically, a universal system with extended rules (without delay) having 10 neurons is constructed.

Linqiang Pan, Xiangxiang Zeng

On the Power of Computing with Proteins on Membranes

P systems with proteins on membranes are inspired closely by switching protein channels. This model of membrane computing using membrane division has been previously shown to solve an NP-complete problem in polynomial time. In this paper we characterize the class of problems solvable by these P systems in polynomial time and we show that it equals

PSPACE

. Therefore, these P systems are computationally equivalent (up to a polynomial time reduction) to the alternating Turing machine or the PRAM computer. The proof technique we employ reveals also some interesting trade-offs between certain P system properties, as antiport rules, membrane labeling by polarization or the presence of proteins.

Petr Sosík, Andrei Păun, Alfonso Rodríguez-Patón, David Pérez

An Efficient Simulation of Polynomial-Space Turing Machines by P Systems with Active Membranes

We show that a deterministic single-tape Turing machine, operating in polynomial space with respect to the input length, can be efficiently simulated (both in terms of time and space) by a semi-uniform family of P systems with active membranes and three polarizations, using only communication rules. Then, basing upon this simulation, we prove that a result similar to the

space hierarchy theorem

can be obtained for P systems with active membranes: the larger the amount of space we can use during the computations, the harder the problems we are able to solve.

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

Look-Ahead Evolution for P Systems

This article introduces a new derivation mode for P systems. This mode permits to evaluate next possible configurations and to discard some of them according to forbidding conditions. The interesting point is that the software implementation of this mode needs very small modifications to the standard algorithm of rule assignment for maximal parallelism. The introduced mode has numerous advantages with respect to the maximally parallel mode, the most important one being that some non-deterministic proofs become deterministic. As an example we present a generalized communicating P system that accepts 2

n

in

n

steps in a deterministic way. Another example shows that in the deterministic case this mode is strictly more powerful than the maximally parallel derivation mode. Finally, this mode gives a natural way to define P systems that may accept or reject a computation.

Sergey Verlan

Backmatter

Weitere Informationen

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.

Whitepaper

- ANZEIGE -

Globales Erdungssystem in urbanen Kabelnetzen

Bedingt durch die Altersstruktur vieler Kabelverteilnetze mit der damit verbundenen verminderten Isolationsfestigkeit oder durch fortschreitenden Kabelausbau ist es immer häufiger erforderlich, anstelle der Resonanz-Sternpunktserdung alternative Konzepte für die Sternpunktsbehandlung umzusetzen. Die damit verbundenen Fehlerortungskonzepte bzw. die Erhöhung der Restströme im Erdschlussfall führen jedoch aufgrund der hohen Fehlerströme zu neuen Anforderungen an die Erdungs- und Fehlerstromrückleitungs-Systeme. Lesen Sie hier über die Auswirkung von leitfähigen Strukturen auf die Stromaufteilung sowie die Potentialverhältnisse in urbanen Kabelnetzen bei stromstarken Erdschlüssen. Jetzt gratis downloaden!

Bildnachweise