Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben

2014 | Buch

A Kernel P Systems Survey Kapitel lesen Erstes Kapitel lesen

Membrane Computing

14th International Conference, CMC 2013, Chişinău, Republic of Moldova, August 20-23, 2013, Revised Selected Papers

herausgegeben von: Artiom Alhazov, Svetlana Cojocaru, Marian Gheorghe, Yurii Rogozhin, Grzegorz Rozenberg, Arto Salomaa

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
insite
SUCHEN

Über dieses Buch

This book constitutes the thoroughly refereed post-conference proceedings of the 14th International Conference on Membrane Computing, CMC 2013, held in Chişinău, Republic of Moldova, in August 2013.

The 16 revised selected papers presented together with 6 invited lectures were carefully reviewed and selected from 26 papers presented at the conference. Membrane computing is an area of computer science aiming to abstract computing ideas and models from the structure and the functioning of living cells, as well as from the way the cells are organized in tissues or higher order structures. It deals with membrane systems, also called P systems, which are distributed and parallel algebraic models processing multi sets of objects in a localized manner (evolution rules and evolving objects are encapsulated into compartments delimited by membranes), with an essential role played by the communication among compartments and with the environment.

Inhaltsverzeichnis

Frontmatter

Invited Papers

A Kernel P Systems Survey
Abstract
In this short paper one overviews the two years development of kernel P systems (kP systems for short), a basic class of P systems combining features of different variants of such systems. The definition of kP systems is given, some examples illustrate various features of the model and the most significant results are presented.
Marian Gheorghe, Florentin Ipate
Roads to New Grand Challenges of Informatics
(Extended Abstract)
Abstract
Currently dominating perception of computer science has its origin in in a very cleverly written, and much influential, paper of Newel, Simon and Perlis, published in Science in 1967, that well captured the perception of the field at that time.
Jozef Gruska
Computational Complexity of P Systems with Active Membranes
Abstract
P systems with active membranes constitute a very interesting model of computation, defined in the framework of Membrane Computing. Since their appeareance, they have been used to solve computationally difficult problems (usually in the classes NP and PSPACE), due to their ability to generate an exponential size workspace in a polynomial number of time steps. Several computational complexity techniques have thus been applied to study their computing power and efficiency. In this extended abstract I will briefly survey some of these techniques and the main results which have been obtained in the last few years by the group of Membrane Computing at the University of Milano-Bicocca (also known as the “Milano Team”), sometimes in collaboration with collegues from the international Membrane Computing community.
Alberto Leporati
Some Open Problems about Catalytic, Numerical, and Spiking Neural P Systems
(Extended Abstract)
Abstract
Some open problems and research topics are pointed, about three classes of P systems: catalytic, numerical, and spiking neural P systems. In each case, several issues are briefly discussed, in general, related to questions already formulated as open problems in the literature and also related to recent results dealing with these questions.
Gheorghe Păun
Active Membranes, Proteins on Membranes, Tissue P Systems: Complexity-Related Issues and Challenges
Abstract
We resume computational complexity aspects of several models of membrane systems, namely P systems with active membranes, P systems with proteins on membranes and tissue P systems both with membrane separation and membrane division. A sequence of common issues is studied in relation to these P system models, and 16 open problems are stated in the text.
We question the role of families of P systems and their necessity to solve computationally hard problems in polynomial time. For each P system model we focus on conditions guaranteeing the polynomial equivalence of families of P systems and Turing machines. The ability of P systems to solve NP/co-NP-complete problems in polynomial time (trading space for time) is a very popular issue. Interesting characterizations of the borderline between tractability and intractability, i.e., P/NP, have been recently shown. Similarly important, although less popular, is the relation between NP/co-NP and further classes as PP, the polynomial hierarchy PH and PSPACE. Several models of P systems has been shown to characterize the class PSPACE which itself characterizes parallel computations with an unlimited number of processors but a limited propagation of data between them.
Petr Sosík
Using the Formal Framework for P Systems
Abstract
In this article we focus on the model called the formal framework for P systems. This model provides a descriptional language powerful enough to represent in a simple way, via a strong bisimulation, most of the variants of P systems. The article presents a series of concrete examples of the application of the formal framework in order to understand, extend, compare and explain different models of P systems leading to new research ideas and open problems.
Sergey Verlan

Regular Papers

A P System for Annotation of Romanian Affixes
Abstract
This paper describes membrane computational models parsing affixed Romanian words with prefixes, suffixes, terminations, alterations in the root, and continues previous works on word derivation modeling. An algorithm for Romanian affixes extraction is given, and several models of P systems are proposed.
Artiom Alhazov, Svetlana Cojocaru, Alexandru Colesnicov, Ludmila Malahov, Mircea Petic
Behavioural Equivalences in Real-Time P Systems
Abstract
We present a real-time extension of P systems in which each membrane and each object has a lifetime attached to it, and we use these lifetimes to define and study various behavioural equivalences. We also establish sufficient conditions for guaranteeing progression over time.
Bogdan Aman, Gabriel Ciobanu
Modelling of Surface Runoff Using 2D P Colonies
Abstract
We continue the investigation of 2D P colonies introduced as a class of abstract computing devices composed of independent agents, acting and evolving in a shared 2D environment where the agents are located. Agents have limited information about the contents of the environment where they can move in four directions. In this paper we continue the research of modelling surface runoff in 2D P colonies. We have added information about flow direction and amount of water in sinks (places without runoff, lakes,...) to the simulation environment. The data from the simulation is compared with the data generated by simulation model of water erosion SIMWE.
Luděk Cienciala, Lucie Ciencialová, Miroslav Langer
Implementation of P Systems by Using Big Data Technologies
Abstract
Due to their inherent parallel and non-deterministic nature, P system implementations require vast computing and storage resources. This significantly limits their applications, even more so when the calculation of all possible evolutions of the P system is required. This article exposes the scalability possibilities available with the Big Data ecosystem for P systems implementations, using Map Reduce parallelism to build the P system computation tree. The Hadoop based implementation is then used for generating test suites for cell like P systems, in particular for context-dependent rule coverage testing. Our preliminary evaluations on a benchmark of automatically generated P systems confirm that the proposed approach scales well.
Alex Ciobanu, Florentin Ipate
On Counter Machines versus dP Automata
Abstract
Continuing the study of connections between classical and P automata variants, we show that dP automata, i.e., distributed systems of P automata, where the input multiset is mapped to the set of strings consisting of all permutations of its elements, are as powerful as the class of distributed systems of special counter machine acceptors. These variants of counter machines read multisets (represented as sets of all permutations of their elements) and manipulate counters in a conventional manner.
Erzsébet Csuhaj-Varjú, György Vaszil
Model Checking Kernel P Systems
Abstract
Recent research in membrane computing examines and confirms the anticipated modelling potential of kernel P systems in several case studies. On the one hand, this computational model is destined to be an abstract archetype which advocates the unity and integrity of P systems onto a single formalism. On the other hand, this envisaged convergence is conceived at the expense of a vast set of primitives and intricate semantics, an exigent context when considering the development of simulation and verification methodologies and tools.
Encouraged and guided by the success and steady progress of similar undertakings, in this paper we directly address the issue of formal verification of kernel P systems by means of model checking and unveil a software framework, kpWorkbench, which integrates a set of related tools in support of our approach.
A case study that centres around the well known Subset Sum problem progressively demonstrates each stage of the proposed methodology: expressing a kP system model in recently introduced kP-Lingua; the automatic translation of this model into a Promela (Spin) specification; the assisted, interactive construction of a set of LTL properties based on natural language patterns; and finally, the formal verification of these properties against the converted model, using the Spin model checker.
Ciprian Dragomir, Florentin Ipate, Savas Konur, Raluca Lefticaru, Laurentiu Mierla
Flattening in (Tissue) P Systems
Abstract
For many models of P systems and tissue P systems, the main behavior of a specific system can be simulated by a corresponding system with only one membrane or cell, respectively; this effective construction is called flattening. In this paper we describe the main procedure of flattening for specific variants of static (tissue) P systems as well as for classes of dynamic (tissue) P systems with a bounded number of possible membrane structures or a bounded number of cells during any computation.
Rudolf Freund, Alberto Leporati, Giancarlo Mauri, Antonio E. Porreca, Sergey Verlan, Claudio Zandron
Solving SAT by P Systems with Active Membranes in Linear Time in the Number of Variables
Abstract
In this paper we solve the SAT problem (the satisfiability problem of propositional formulas in conjunctive normal form) by two polynomially uniform families of P systems with active membranes. The novelty of these solutions is that these P systems can solve the SAT problem in linear time in the number of propositional variables occurring in the input. This means that the number of computation steps is independent form the number of clauses of the input. To achieve this efficiency our systems employ only the standard rules of P systems with active membranes plus membrane creation rules. Moreover, in the first solution the P systems do not use the polarizations of the membranes but use such membrane division rules which can change the labels of the involved membranes. In the second solution the P systems do not employ membrane label changing but use the polarizations of the membranes instead.
Zsolt Gazdag
On Communication Complexity of Some Hard Problems in ECPe Systems
Abstract
In this paper, we present non-confluent solutions to some NP-complete problems using recognizer Evolution-Communication P systems with Energy (ECPe systems). We then evaluate the communication resources used in these systems using dynamical communication measures proposed for computations in ECPe systems. Specifically, we evaluate based on number of communication steps, communication rules and energy required for all communication.
Nestine Hope S. Hernandez, Richelle Ann B. Juayong, Henry N. Adorna
About One-Sided One-Symbol Insertion-Deletion P Systems
Abstract
In this article we consider insertion-deletion P systems inserting or deleting one symbol in one or two symbol(s) left context (more precisely of size (1,2,0;1,1,0) and (1,1,0;1,2,0)). We show that computational completeness can be achieved by using only 3 membranes in a tree-like structure. Hence we obtain a trade-off between the sizes of contexts of insertion and deletion rules and the number of membranes sufficient for computational completeness.
Sergiu Ivanov, Sergey Verlan
Flattening and Simulation of Asynchronous Divisionless P Systems with Active Membranes
Abstract
We prove that asynchronous P systems with active membranes without division rules can be simulated by single-membrane transition P systems using cooperative rules, even if the synchronisation mechanisms provided by electrical charges and membrane dissolution are exploited. In turn, the latter systems can be simulated by means of place/transition Petri nets, and hence all these models are computationally weaker than Turing machines.
Alberto Leporati, Luca Manzoni, Antonio E. Porreca
Enzymatic Numerical P Systems Using Elementary Arithmetic Operations
Abstract
We prove that all-parallel enzymatic numerical P systems whose production functions can be expressed as a combination of sums, differences, products and integer divisions characterise PSPACE when working in polynomial time. We also show that, when only sums and differences are available, exactly the problems in P can be solved in polynomial time. These results are proved by showing how EN P systems and random access machines, running in polynomial time and using the same basic operations, can simulate each other efficiently.
Alberto Leporati, Giancarlo Mauri, Antonio E. Porreca, Claudio Zandron
Communication Rules Controlled by Generated Membrane Boundaries
Abstract
In natural processes, the events represented by communication rules in membrane computing are taken place in the vicinity of membranes. Looking at regions as multisets, partial approximation spaces generalized for multisets give a plausible opportunity to model membrane boundaries in an abstract way. Thus, motivated by natural phenomena, the abstract notion of “to be close enough to a membrane” can be built in membrane computing. Restricting communication rules to these boundaries, the interactions along the membranes can be controlled locally during the membrane computations.
Tamás Mihálydeák, Zoltán Ernő Csajbók, Péter Takács
Programming P Systems with Complex Objects
Abstract
We develop and formalise our earlier complex objects proposal and show that it enables an efficient high-level programming of P systems.
Radu Nicolescu, Florentin Ipate, Huiling Wu
In Search of a Structure of Fractals by Using Membranes as Hyperedges
Abstract
The internal structure of the iterations of Koch curve and Sierpiński gasket—the known fractals [4]—is described in terms of multi-hypergraphical membrane systems related to membrane structures [13] and whose membranes are hyperedges of multi-hypergraphs used to define gluing patterns for the components of the iterations of the considered fractals.
Adam Obtułowicz
The Relevance of the Environment on the Efficiency of Tissue P Systems
Abstract
The efficiency of computational devices is usually expressed in terms of their capability to solve computationally hard problems in polynomial time. This paper focuses on tissue P systems, whose efficiency has been shown for several scenarios where the number of cells in the system can grow exponentially, e.g. by using cell division rules or cell separation rules. Moreover, in the first case it suffices to consider very short communication rules with length bounded by two, and in the second one it is enough to consider communication rules with length at most three. This kind of systems have an environment with the property that objects initially located in it appear in an arbitrarily large number of copies, which is a somewhat unfair condition from a computational complexity point of view. In this context, we study the role played by the environment and its ability to handle infinitely many objects, in particular we consider tissue P systems whose environment is initially empty.
Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Miquel Rius-Font, Luis Valencia-Cabrera
Backmatter
Metadaten
Titel
Membrane Computing
herausgegeben von
Artiom Alhazov
Svetlana Cojocaru
Marian Gheorghe
Yurii Rogozhin
Grzegorz Rozenberg
Arto Salomaa
Copyright-Jahr
2014
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-54239-8
Print ISBN
978-3-642-54238-1
DOI
https://doi.org/10.1007/978-3-642-54239-8

Premium Partner

    Bildnachweise