BWMC2016. Brainstorming Week on Membrane Computing (14th. 2016. Sevilla)

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

Examinar

Mostrando 1 - 20 de 27

On the complexity of active P systems
(Fénix, 2016) Román, Gábor
We are going to present a polynomially uniform solution to the Quanti ed 3SAT decision problem with restricted instances where the quanti ers alternate, based on recognizer P systems with active membranes and no input membrane, having three polarizations using only dissolution and division rules.
Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes
(Fénix, 2016) Gazdag, Zsolt; Kolonits, Gábor
In this paper we consider three restricted variants of P systems with active membranes: (1) P systems using out communication rules only, (2) P systems using elementary membrane division and dissolution rules only, and (3) polarizationless P systems using dissolution and restricted evolution rules only. We show that every problem in P can be solved with uniform families of any of these variants. This, using known results on the upper bound of the computational power of variants (1) and (3) yields new characterizations of the class P. In the case of variant (2) we provide a further characterization of P by giving a semantic restriction on the computations of P systems of this variant
Individual memory about the 14th Brainstorming Week on Membrane Computing
(Fénix, 2016) Ribes Metidieri, Ariadna
The main objective of this memory is to stand out one of the research methods for developing new P system models observed during the 14th Brainstorming Week on Membrane Computing. Firstly, a general overview of P systems is provided. To continue, the use of register machines in order to justify completeness and universality is justi ed. And to end up, an example of the method is provided.
Building a basic membrane computer
(Fénix, 2016) Millán Calderón, Alejandro; Viejo Cortés, Julián; Quirós Carmona, Juan; Bellido Díaz, Manuel Jesús; Guerrero Martos, David; Ostúa Arangüena, Enrique; Universidad de Sevilla. Departamento de Tecnología Electrónica; Universidad de Sevilla, TIC204: Investigación y Desarrollo Digital
In this work, we present the building of two well-known membrane com- puters (squares generator and divisor test). Although they are very basic machines they present problems common to every P system (competition, parallel execution of rules, membrane dissolution, etc.) that have to be solved in order to get real emulations for them. The presented designs mimic the systems operation in a realistic way, by achieving both maximum parallelism and non-determinism, and demonstrating for the rst time that a membrane computer can actually be built in silico. Our architectures fully emu- late the membranes behaviour yielding to a performance of one transition per clock cycle, supposing a real physical realization of the mentioned machines.
Generalized P Colonies with passive environment
(Fénix, 2016) Ciencialová, Lucie; Cienciala, Ludek; Sosík, Petr; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
We study two variants of P colonies with initial content of P colony and so called passive environment: P colonies with two objects inside each agent that can only consume or generate objects, and P colonies with one object inside each agent using rewriting and communication rules. We show that the rst kind of P colonies with one consumer agent and one sender agent can generate all sets of natural numbers computed by register machines, and hence they are computationally universal in the Turing sense. Similarly, also the second kind of systems with three agents with rewriting/consuming rules is computationally complete. The paper improves previously published universality results concerning generalized P colonies, and it also extends our knowledge about very simple multi-agent systems capable of universal computation.
Semantics of Deductive Databases in a Membrane Computing Connectionist Model
(Fénix, 2016) Díaz Pernil, Daniel; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII); Universidad de Sevilla. TIC193 : Computación Natural; Universidad de Sevilla. FQM296 : Topología Computacional y Matemática Aplicada
The integration of symbolic reasoning systems based on logic and connectionist systems based on the functioning of living neurons is a vivid research area in computer science. In the literature, one can found many e orts where di erent reasoning systems based on di erent logics are linked to classic arti cial neural networks. In this paper, we study the relation between the semantics of reasoning systems based on propositional logic and the connectionist model in the framework of membrane computing, namely, spiking neural P systems. We prove that the xed point semantics of deductive databases and the immediate consequence operator can be implemented in the spiking neural P systems model.
Solving the 3-COL Problem by Using Tissue P Systems without Environment and Proteins on Cells
(Fénix, 2016) Díaz Pernil, Daniel; Christinal, Hepzibah A.; Gutiérrez Naranjo, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII); Universidad de Sevilla. TIC193 : Computación Natural; Universidad de Sevilla. FQM296 : Topología Computacional y Matemática Aplicada
The 3-COL problem consists on deciding if the regions of a map can be coloured with only three colors bearing in mind that two adjacent regions must be coloured with di erent colors. It is a NP problem and it has been previously used in complexity studies in membrane computing to check the ability of a model for solving problems of such complexity class. Recently, tissue P systems with proteins on cells have been presented and its ability to solve NP-problems has been proved, but it remained as an open question to know if such model was still able to solve such problems if the environment was removed. In this paper we provide an a rmative answer to this question by showing a uniform family of tissue P systems without environment and with proteins on cells which solves the 3-COL problem in linear time.
Stern-Gerlach Experiment
(Fénix, 2016) Arazo, María; Barroso Mancha, Marc; Torre, Óscar de la; Moreno Valero, Laura; Ribes Metidieri, Ariadna; Ribes Metidieri, Patricia; Ventura, Ana; Orellana Martín, David; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193 : Computación Natural
This work is about modelling an experiment composed by multiple Stern- Gerlach devices using Membrane Computing. We will study the behaviour of a set of independent particles passing through three linked Stern-Gerlach devices and discarting the spin down particles after passing through the first one, taking profit of the Membrane Computing’s ability of running parallel processing. Using a cell-like model to describe the system and testing it using the P-lingua framework we have obtained the theorically predicted results when the number of initial multisets is high enough.
A Toolbox for Simpler Active Membrane Algorithms
(Fénix, 2016) Leporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca, Antonio E.; Zandron, Claudio
We show that recogniser P systems with active membranes can be augmented with a priority over their set of rules and any number of membrane charges without loss of generality, as they can be simulated by standard P systems with active membranes, in particular using only two charges. Furthermore, we show that more general accepting conditions, such as sending out several, possibly contradictory results and keeping only the first one, or rejecting by halting without output, are also equivalent to the standard accepting conditions. The simulations we propose are always without significant loss of efficiency, and thus the results of this paper can hopefully simplify the design of algorithms for P systems with active membranes.
Extended SNP Systems with States
(Fénix, 2016) Alhazov, Artiom; Freund, Rudolf; Ivanov, Sergiu
We consider (extended) spiking neural P systems with states, where the applicability of rules in a neuron not only depends on the presence of su ciently many spikes (yet in contrast to the standard de nition, no regular checking sets are used), but also on the current state of the neuron. Moreover, a spiking rule not only sends spikes, but also state information to the connected neurons. We prove that this variant of the original model of extended spiking neural P systems can simulate register machines with only two states, even in the basic non-extended variant.
On the 14th BWMC
(Fénix, 2016) Arazo, María
Complexity of Simulating R Systems by P Systems
(Fénix, 2016) Alhazov, Artiom; Aman, Bogdan; Freund, Rudolf; Ivanov, Sergiu
We show multiple ways to simulate R systems by non-cooperative P systems with atomic control by promoters and/or inhibitors, or with matter-antimatter annihi- lation rules, with a slowdown by a factor of constant. The descriptional complexity is also linear with respect to that of simulated R system. All these constants depend on how general the model of R systems is, as well as on the chosen control ingredients of P systems. Special attention is paid to the di erences in the mode of rule application in these models.
Uranium- decay chain
(Fénix, 2016) Arazo, María; Barroso Mancha, Marc; Torre, Óscar de la; Moreno Valero, Laura; Ribes Metidieri, Ariadna; Ribes Metidieri, Patricia; Ventura, Ana; Orellana Martín, David; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193 : Computación Natural
The main objective of this article is to modelize the process of decay of Uranium within the framework of Membrane Computing, so the evolution of great numbers of particles can be progressively followed and the results of the desintegrations (nuclei coming from and − decays) can be counted. In order to model the process in an accurate manner, exploiting the properties of maximal parallelism and non-determinism of Membrane Computing, a Population Dynamic P system (or PDP for short) restricted to one environment and a P system conformed by only the skin have been selected. The difficulty in the characterisation of this reactions lays in the simultaneity of the different decays, since the number of desintegrations of nucleous of each specie depend on the number of atoms of the initial population. In order to solve this problem and keep their attachment, the characteristic time of production of each decay has been translated into probabilities of deintregration of a nucleous using the decay constant .
14th Brainstorming Week on Membrane Computing Sevilla, February 1 - 5, 2016 : RGNC Report 1/2016
(Fénix, 2016) Graciani Díaz, Carmen; Orellana Martín, David; Riscos Núñez, Agustín; Romero Jiménez, Álvaro; 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
Individual memory about the 14th Brainstorming Week on Membrane Computing
(Fénix, 2016) Ventura, Ana
Computational Completeness of P Systems Using Maximal Variants of the Set Derivation Mode
(Fénix, 2016) Alhazov, Artiom; Freund, Rudolf; Verlan, Sergey
We consider P systems only allowing rules to be used in at most one copy in each derivation step, especially the variant of the maximally parallel derivation mode where each rule may only be used at most once. Moreover, we also consider the derivation mode where from those sets of rules only those are taken which have the maximal number of rules. We check the computational completeness proofs of several variants of P systems and show that some of them even literally still hold true for the for these two new set derivation modes. Moreover, we establish two new results for P systems using target selection for the rules to be chosen together with these two new set derivation modes.
Improving Simulations of Spiking Neural P Systems in NVIDIA CUDA GPUs: CuSNP
(Fénix, 2016) Carandang, Jym Paul; Villaflores, John Matthew B.; Cabarle, Francis George C.; Adorna, Henry N.; Martínez del Amor, Miguel Ángel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193 : Computación Natural
Spiking neural P systems (in short, SN P systems) are parallel models of computations inspired by the spiking ( ring) of biological neurons. In SN P systems, neurons function as spike processors and are placed on nodes of a directed graph. Synapses, the connections between neurons, are represented by arcs or directed endges in the graph. Not only do SN P systems have parallel semantics (i.e. neurons operate in parallel), but their structure as directed graphs allow them to be represented as vectors or matrices. Such representations allow the use of linear algebra operations for simulating the evolution of the system con gurations, i.e. computations. In this work, we continue the implementations of SN P systems with delays, i.e. a delay is associated with the sending of a spike from a neuron to its neighbouring neurons. Our implementation is based on a modi ed representation of SN P systems as vectors and matrices for SN P systems without delays. We us massively parallel processors known as graphics processing units (in short, GPUs) from NVIDIA. For experimental validation, we use SN P systems implementing generalized sorting networks. We report a speedup, i.e. the ratio between the running time of the sequential over the parallel simulator, of up to approximately 51 times for a 512-size input to the sorting network.
Minimal cooperation in polarizationless P systems with active membranes
(Fénix, 2016) Valencia Cabrera, Luis; Orellana Martín, David; 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
P systems with active membranes is a well developed framework in the eld of Membrane Computing. Using evolution, communication, dissolution and division rules, we know that some kinds of problems can be solved by those systems, but taking into account which ingredients are used. All these rules are inspired by the behavior of living cells, who \compute" with their proteins in order to obtain energy, create components, send information to other cells, kill themselves (in a process called apoptosis), and so on. But there are other behaviors not captured in this framework. As mitosis is simulated by division rules (for elementary and non-elementary membranes), meiosis, that is, membrane ssion inspiration is captured in separation rules. It di ers from the rst in the sense of duplication of the objects (that is, in division rules, we duplicate the objects not involved in the rule, meanwhile in separation rules we divide the content of the original membrane into the new membranes created). Evolution rules simulate the transformation of components in membranes, but it is well known that elements interact with another ones in order to obtain new components. Cooperation in evolution rules is considered. More speci cally, minimal cooperation (in the sense that only two objects can interact in order to create one or two objects)
Kernel P Systems Modelling, Testing and Veri cation
(Fénix, 2016) Gheorghe, Marian; Ceterchi, Rodica; Ipate, Florentin; Konur, Savas
A kernel P system (kP system, for short) integrates in a coherent and elegant manner many of the P system features most successfully used for modelling various applications and, consequently, it provides a framework for analyzing these models. In this paper, we illustrate the modeling capabilities of kernel P systems by showing how other classes of P systems can be represented with this formalism and providing a number of kP system models for sorting algorithms. Furthermore, the problem of testing systems modelled as kP systems is also discussed and a test generation method based on automata is proposed. We also demonstrate how formal veri cation can be used to validate that the given models work as desired.
Purely Catalytic P Systems over Integers and Their Generative Power
(Fénix, 2016) Alhazov, Artiom; Belingheri, Omar; Freund, Rudolf; Ivanov, Sergiu; Porreca, Antonio E.; Zandron, Claudio
We further investigate the computing power of the recently introduced P systems with Z-multisets (also known as hybrid sets) as generative devices. These systems apply catalytic rules in the maximally parallel way, even consuming absent non-catalysts, e ectively generating vectors of arbitrary (not just non-negative) integers. The rules may be made inapplicable only by dissolution rules. However, this releases the catalysts into the immediately outer region, where new rules might become applicable to them. We discuss the generative power of this model. Finally, we consider the variant with mobile catalysts.

Examinar

Examinando BWMC2016. Brainstorming Week on Membrane Computing (14th. 2016. Sevilla) por Fecha de publicación