BWMC2017: Brainstorming Week on Membrane Computing (15th. 2017. Sevilla)

URI permanente para esta colecciónhttps://hdl.handle.net/11441/55974

Examinar

Mostrando 1 - 14 de 14

On Efficiency of P Systems with Symport/Antiport and Membrane Division
(Fenix Editora, 2017) Macías Ramos, Luis Felipe; Song, Bosheng; Song, Tao; Pan, Linqiang; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Ciencia e Innovación (MICIN). España; Universidad de Sevilla. TIC193: Computación Natural
Classical membrane systems with symport/antiport rules observe the con- servation law, in the sense that they compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. In these systems the environment plays an active role because the systems not only send objects to the environment, but also bring objects from the environment. In the initial configuration of a system, there is a special alphabet whose elements appear in an arbitrary large number of copies. The ability of these computing devices to have infinite copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems. This paper deals with computational aspects of P systems with symport/antiport and membrane division rules where there is not an environment having the property mentioned above. Specifically, we establish the relationships between the polynomial complexity class associated with P systems with symport/antiport, membrane division rules, and with or without environment. As a consequence, we prove that the role of the environment is irrelevant in order to solve NP–complete problems in an efficient way.
Membrane Computing Applications in Computational Economics
(Fenix Editora, 2017) Sánchez Karhunen, Eduardo; Valencia Cabrera, Luis; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
Major efforts have been made along the last decade on the modelling and simulation of phenomena within areas such as Biochemistry, Ecology or Robotics, providing solutions for relevant problems (signalling pathways, population dynamics or logic gene networks, or robot control and planning, among others). However, other areas initially explored have not received the same amount of attention. This is the case of computational economics, where an initial model of the so-called producer-retailer problem was proposed by Gh. and R. P aun making use of membrane computing modelling and simulation tools. In the present paper, we start designing a solution for that problem based on PDP systems, obtaining results comparable with the foundational paper. Then, an enhanced and enriched model is proposed, including several economic issues not considered in the initial model as: depreciation of production capacity, capacity increase decision mechanism, dividends payment and costs associated to production factors. Additionally, both models have been simulated making use of the framework provided by P-Lingua and MeCoSim, and delivering a custom application based on them to reproduce the virtual experiments. Finally, several scenarios have been analysed focusing on different elements included in the model.
Subroutines in P Systems and Closure Properties of Their Complexity Classes
(Fenix Editora, 2017) Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio
The literature on membrane computing describes several variants of P systems whose complexity classes C are "closed under exponentiation", that is, they satisfy the inclusion PC C, where PC is the class of problems solved by polynomial-time Turing machines with oracles for problems in C. This closure automatically implies closure under many other operations, such as regular operations (union, concatenation, Kleene star), intersection, complement, and polynomial-time mappings, which are inherited from P. Such results are typically proved by showing how elements of a family of P systems can be embedded into P systems simulating Turing machines, which exploit the elements of as subroutines. Here we focus on the latter construction, abstracting from the technical details which depend on the speci c variant of P system, in order to describe a general strategy for proving closure under exponentiation.
Unfair P Systems
(Fenix Editora, 2017) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu
We introduce a novel kind of P systems in which the application of rules in each step is controlled by a function on the applicable multisets of rules. Some examples are given to exhibit the power of this general concept. Moreover, for three well-known models of P systems we show how they can be simulated by P systems with a suitable fairness function.
P Systems with Active Cells
(Fenix Editora, 2017) Orellana Martín, David; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
P systems with active membranes is a widely studied framework within the field of Membrane Computing since the creation of the discipline. The abstraction of the structure and behavior of living cells is reflected in the tree-like hierarchy and the kinds of rules that can be used in these kinds of systems. Resembling the organization and communication between cells within tissues that form organs, tissue-like P systems were defined as their abstractions, using symport/antiport rules, that is, moving and exchanging elements from one cell to another one. All the cells are located in an environment where there exist an arbitrary number of some elements. Lately, symport/antiport rules have been used in the framework of cell-like membrane systems in order to study their computational power. Interesting results have been reached, since they act similarly to their counterparts in the framework of tissue P systems. Here, the use of the former defined rules (that is, evolution, communication, dissolution and division/separation rules) is considered, but not working with a tree-like structure. Some remarks about choosing good semantics are given.
Membrane Systems and Time Petri Nets
(Fenix Editora, 2017) Aman, Bogdan; Battyányi, Péter; Ciobanu, Gabriel; Vaszil, György
We investigate the relationship of time Petri nets and di erent variants of membrane systems. First we show that the added feature of \time" in time Petri nets makes it possible to simulate the maximal parallel rule application of membrane systems without introducing maximal parallelism to the Petri net semantics, then we de ne local time P systems and explore how time Petri nets and the computations of local time P systems can be related.
Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Inwards
(Fenix Editora, 2017) Valencia Cabrera, Luis; Orellana Martín, David; Martínez del Amor, Miguel Ángel; Riscos Núñez, Agustín; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P. P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally effi cient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide effi cient solutions to NP{complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational e fficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted.
Two Notes on APCol Systems
(Fenix Editora, 2017) Ciencialová, Lucie; Cienciala, Ludek
In this work, we continue our research in the eld of string processing mem- brane systems - APCol systems. We focus on a relation of APCol systems with PM colonies - colonies whose agents can only perform point mutation transformations of the common string, in a vicinity of the agent. The second part is devoted to a connection of APCol systems and logic circuits using AND, OR and NOT gates.
Time-freeness and Clock-freeness and Related Concepts in P Systems
(Fenix Editora, 2017) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu; Pan, Linqiang; Song, Bosheng
In the majority of models of P systems, rules are applied at the ticks of a global clock and their products are introduced into the system for the following step. In timed P systems, di erent integer durations are statically assigned to rules; time-free P systems are P systems yielding the same languages independently of these durations. In clock-free P systems, durations are real and are assigned to individual rule applications; thus, different applications of the same rule may last for a different amount of time. In this paper, we formalise timed, time-free, and clock-free P system within a framework for generalised parallel rewriting. We then explore the relationship between these variants of semantics. We show that clock-free P systems cannot effi ciently solve intractable problems. Moreover, we consider un-timed systems where we collect the results using arbitrary timing functions as well as un-clocked P systems where we take the union over all possible per-instance rule durations. Finally, we also introduce and study mode-free P systems, whose results do not depend on the choice of a mode within a fixed family of modes, and compare mode-freeness with clock-freeness.
Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Outwards
(Fenix Editora, 2017) Valencia Cabrera, Luis; Orellana Martín, David; Martínez del Amor, Miguel Ángel; Riscos Núñez, Agustín; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P. P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally e fficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class P can be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide e cient solutions to NP{complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational e fficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted.
P Systems with Randomized Right-hand Sides of Rules
(Fenix Editora, 2017) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu
P systems are a model of hierarchically compartmentalized multiset rewriting. We introduce a novel kind of P systems in which rules are dynamically constructed in each step by non-deterministic pairing of left-hand and right-hand sides. We de ne three variants of right-hand side randomization and compare each of them with the power of conventional P systems. It turns out that all three variants enable non-cooperative P systems to generate exponential (and thus non-semi-linear) number languages. We also give a binary normal form for one of the variants of P systems with randomized rule right-hand sides. Finally, we also discuss extensions of the three variants to tissue P systems, i.e., P systems on an arbitrary graph structure.
15th Brainstorming Week on Membrane Computing Sevilla, January 31 - February 3, 2017, RGNC REPORT 1/2017 Research Group on Natural Computing Sevilla University
(Fenix Editora, 2017) Graciani Díaz, Carmen; Paun, Gheorghe; Riscos Núñez, Agustín; Valencia Cabrera, Luis; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Research Group on Natural Computing; Universidad de Sevilla. TIC193: Computación Natural
Sparse-matrix Representation of Spiking Neural P Systems for GPUs
(Fenix Editora, 2017) Martínez del Amor, Miguel Ángel; Orellana Martín, David; Cabarle, Francis George C.; Pérez Jiménez, Mario de Jesús; Adorna, Henry N.; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
Current parallel simulation algorithms for Spiking Neural P (SNP) systems are based on a matrix representation. This helps to harness the inherent parallelism in algebraic operations, such as vector-matrix multiplication. Although it has been convenient for the rst parallel simulators running on Graphics Processing Units (GPUs), such as CuSNP, there are some bottlenecks to cope with. For example, matrix representation of SNP systems with a low-connectivity-degree graph lead to sparse matrices, i.e. containing more zeros than actual values. Having to deal with sparse matrices downgrades the performance of the simulators because of wasting memory and time. However, sparse matrices is a known problem on parallel computing with GPUs, and several solutions and algorithms are available in the literature. In this paper, we brie y analyse some of these ideas and apply them to represent some variants of SNP systems. We also conclude which variant better suit a sparse-matrix representation.
Limits on Efficient Computation in P Systems with Symport/Antiport Rules
(Fenix Editora, 2017) Macías Ramos, Luis Felipe; Song, Bosheng; Song, Tao; Pan, Linqiang; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Ciencia e Innovación (MICIN). España; Universidad de Sevilla. TIC193: Computación Natural
Classical membrane systems with symport/antiport rules observe the con- servation law, in the sense that they compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. In these systems the environment plays an active role because the systems not only send objects to the environment, but also bring objects from the environment. In the initial configuration of a system, there is a special alphabet whose elements appear in an arbitrary large number of copies. The ability of these computing devices with infinite copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems. This paper deals with computational aspects of P systems with symport/antiport rules and membrane division rules or membrane separation rules. Specifically, we study the limitations of such P systems when the only communication rules allowed have length 1.

Examinar

Examinando BWMC2017: Brainstorming Week on Membrane Computing (15th. 2017. Sevilla) por Fecha de publicación