BWMC2009. Brainstorming Week On Membrane Computing (7th. 2009. Sevilla)
URI permanente para esta colecciónhttps://hdl.handle.net/11441/34358
Examinar
Envíos recientes
Libro Seventh Brainstorming Week on Membrane Computing. Sevilla, February 2-February 6, 2009, Volume II : RGNC REPORT 2/2009(Fénix Editora, 2009) Martínez del Amor, Miguel Ángel; Orejuela Pinedo, Enrique Francisco; Paun, Gheorghe; Pérez Hurtado de Mendoza, Ignacio; Riscos Núñez, Agustín; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Research Group on Natural Computing; Universidad de Sevilla. TIC193: Computación NaturalLibro Seventh Brainstorming Week on Membrane Computing. Sevilla, February 2-February 6, 2009 Volume I : RGNC REPORT 1/2009(Fénix Editora, 2009) Gutiérrez Escudero, Rosa; Gutiérrez Naranjo, Miguel Ángel; Paun, Gheorghe; Pérez Hurtado de Mendoza, Ignacio; Riscos Núñez, Agustín; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Research Group on Natural Computing; Universidad de Sevilla. TIC193: Computación NatualPonencia About the Efficiency of Spiking Neural P Systems(Fénix Editora, 2009) Wang, Jun; Ishdorj, Tseren-Onolt; Pan, LinqiangSpiking neural P systems were proved to be Turing complete as function computing or number generating devices. Moreover, it has been considered in several papers that spiking neural P systems are also computationally efficient devices working in a non-deterministic way or with exponential pre-computed resources. In this paper, neuron budding rules are introduced in the framework of spiking neural P systems, which is biologically inspired by the growth of dendritic tree of neuron. Using neuron budding rules in SN P systems is a way to trade space for time to solve computational intractable problems. The approach is examined here with a deterministic and polynomial time solution to sat problem without using exponential pre-computed resources.Ponencia Parallel Graph Rewriting Systems(Fénix Editora, 2009) Sburlan, DragosPonencia Introducing a Space Complexity Measure for P Systems(Fénix Editora, 2009) Porreca, Antonio E.; Leporati, Alberto; Mauri, Giancarlo; Zandron, ClaudioWe define space complexity classes in the framework of membrane computing, giving some initial results about their mutual relations and their connection with time complexity classes, and identifying some potentially interesting problems which require further research.Ponencia A Bibliography of Spiking Neural P Systems(Fénix Editora, 2009) Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación NaturalPonencia Some Open Problems Collected During 7th BWMC(Fénix Editora, 2009) Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación NaturalA few open problems and research topics collected during the 7th Brain- storming Week on Membrane Computing are briefly presented; further details can be found in the papers included in the volume.Ponencia Efficiency of Tissue P Systems with Cell Separation(Fénix Editora, 2009) 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 Educación y Ciencia (MEC). España; Junta de Andalucía; Universidad de Sevilla. TIC193: Computación NaturalThe most investigated variants of P systems in the last years are cell-like models, especially in terms of efficiency. Recently, different new models of tissue-like (symport/antiport) P systems have received important attention. This paper presents a new class of tissue P systems with cell separation, where cell separation can generate new workspace. Its efficiency is investigated, specifically, (a) only tractable problem can be efficiently solved by using cell separation and communication rules with length at most 1, and (b) an efficient (uniform) solution to SAT problem by using cell separation and communication rules with length at most 6 is presented. Further research topics and open problems are discussed, too.Ponencia Spiking Neural P Systems with Neuron Division and Budding(Fénix Editora, 2009) Pan, Linqiang; Paun, Gheorghe; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Junta de Andalucía; Universidad de Sevilla. TIC193: Computación NaturalIn order to enhance the e±ciency of spiking neural P systems, we introduce the features of neuron division and neuron budding, which are processes inspired by neural stem cell division. As expected (as it is the case for P systems with active membranes), in this way we get the possibility to solve computationally hard problems in polynomial time. We illustrate this possibility with SAT problem.Ponencia Spiking Neural P Systems with Anti-Spikes(Fénix Editora, 2009) Pan, Linqiang; Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación NaturalBesides usual spikes employed in spiking neural P systems, we consider "anti-spikes", which participate in spiking and forgetting rules, but also annihilate spikes when meeting in the same neuron. This simple extension of spiking neural P systems is shown to considerably simplify the universality proofs in this area: all rules become of the form bc ! b0 or bc ! ¸, where b; b0 are spikes or anti-spikes. Therefore, the regular expressions which control the spiking are the simplest possible, identifying only a singleton. A possible variation is not to produce anti-spikes in neurons, but to consider some "inhibitory synapses", which transform the spikes which pass along them into anti- spikes. Also in this case, universality is rather easy to obtain, with rules of the above simple forms.Ponencia New Normal Forms for Spiking Neural P Systems(Fénix Editora, 2009) Pan, Linqiang; Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación NaturalWe consider a natural restriction in the architecture of a spiking neural P system, namely, to have neurons of a small number of types (i.e., using a small number of sets of rules), and we prove that three types of neurons are su±cient in order to generate each recursively enumerable set of numbers as the distance between the first two spikes emitted by the system or as the number of spikes in a specified neuron, in the halting configuration. The case we investigate is that of spiking neural P systems with standard rules, with delays, but without using forgetting rules; similar normal forms remain to be found for other types of systems.Ponencia The Discovery of Initial Fluxes of Metabolic P Systems(Fénix Editora, 2009) Pagliarini, Roberto; Manca, VincenzoA central issue in systems biology is the study of efficient methods to infer fluxes of biological reactions starting from experimental data. Among the different techniques proposed in the last years, in the theory of Metabolic P systems Log-Gain principles have been introduced, which prove to be helpful for deducing biological fluxes from temporal series of observed dynamics. However, crucial tasks remain to be performed for a complete suitable application of these principles. In particular the algebraic systems introduced by the Log-Gain principles require the knowledge of the initial fluxes associated with a set of biochemical reactions. In this paper we propose an algorithm for estimating initial fluxes, which is tested in two case studies.Ponencia Spiking Neural P Systems and Modularization of Complex Networks from Cortical Neural Network to Social Networks(Fénix Editora, 2009) Obtulowicz, AdamAn idea of modularization of complex networks (from cortial neural net, Internet computer network, to market and social networks) is explained and some its topic motivations are presented. Then some known modularization algorithms and modular architectures (constructions) of complex networks are discussed in the context of possible applications of spiking neural P systems in order to improve these modularization algorithms and to analyze massively parallel processes in networks of modular architecture.Ponencia Structured Modeling with Hyperdag P Systems: Part A(Fénix Editora, 2009) Nicolescu, Radu; Dinneen, Michael J.; Kim, Yun-BumP systems provide a computational model based on the structure and interaction of living cells. A P system consists of a hierarchical nesting of cell-like membranes, which can be visualized as a rooted tree. Although the P systems are computationally complete, many real world models, e.g., from socio-economic systems, databases, operating systems, distributed systems, seem to require more expressive power than provided by tree structures. Many such systems have a primary tree-like structure completed with shared or secondary communication channels. Modeling these as tree-based systems, while theoretically possible, is not very appealing, because it typically needs artificial extensions that introduce additional complexities, nonexistent in the originals. In this paper we propose and define a new model that combines structure and flexibility, called hyperdag P systems, in short, hP systems, which extend the definition of conventional P systems, by allowing dags, interpreted as hypergraphs, instead of trees, as models for the membrane structure. We investigate the relation between our hP systems and neural P systems. Despite using an apparently less powerful structure, i.e., a dag instead of a general graph, we argue that hP systems have essentially the same computational power as tissue and neural P systems. We argue that hP systems offer a structured approach to membrane-based modeling that is often closer to the behavior and underlying structure of the modeled objects. Additionally, we enable dynamical changes of the rewriting modes (e.g., to alternate between determinism and parallelism) and of the transfer modes (e.g., the switch between unicast or broadcast). In contrast, classical P systems, both tree and graph based P systems, seem to focus on a statical approach. We support our view with a simple but realistic example, inspired from computer networking, modeled as a hP system with a shared communication line (broadcast channel). In Part B of this paper we will explore this model further and support it with a more extensive set of examples.Ponencia The Computational Complexity of Uniformity and Semi-uniformity in Membrane Systems(Fénix Editora, 2009) Murphy, Niall; Woods, DamienWe investigate computing models that are presented as families of finite computing devices with a uniformity condition on the entire family. Examples include circuits, membrane systems, DNA computers, cellular automata, tile assembly systems, and so on. However, in this list there are actually two distinct kinds of uniformity conditions. The first is the most common and well-understood, where each input length is mapped to a single computing device that computes on the finite set of inputs of that length. The second, called semi-uniformity, is where each input is mapped to a computing device for that input. The former notion is well-known and used in circuit complexity, while the latter notion is frequently found in literature on nature-inspired computing models, from the past 20 years or so. Are these two notions distinct or not? For many models it has been found that these notion are in fact the same, in the sense that the choice of uniformity or semi-uniformity leads to characterisations of the same complexity classes. Here, we buck this trend and show that these notions are actually distinct: we give classes of uniform membrane systems that are strictly weaker than their semi-uniform counterparts. This solves a known open problem in the theory of membrane systems.Ponencia Sleep-Awake Switch with Spiking Neural P Systems: A Basic Proposal and New Issues(Fénix Editora, 2009) Mingo, Jack MarioSpiking Neural P Systems are a kind of Membrane Systems developed with the aim of incorporating ideas from biological systems, known as spiking neurons, in the computational field. Initially, these systems were designed to take concepts of the neural science based on action potentials with the purpose of testing its possibilities from a computational point of view and not to be used as neurological models. In this work, a basic approach in the opposite sense is reviewed by means of the application of such systems on a well-known biological phenomenon. This phenomenon refers to the fluctuations among neural circuits which are responsible for swapping between awake- asleep states. This basic approach is analyzed and new issues are exposed.Ponencia Simulation of Recognizer P Systems by Using Manycore GPUs(Fénix Editora, 2009) Martínez del Amor, Miguel Ángel; Pérez Hurtado de Mendoza, Ignacio; Pérez Jiménez, Mario de Jesús; Cecilia, José M.; Guerrero, Ginés D.; García, José M.; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Educación y Ciencia (MEC). España; Junta de Andalucía; Universidad de Sevilla. TIC193: Computación NaturalSoftware development for cellular computing is growing up yielding new applications. In this paper, we describe a simulator for the class of recognizer P systems with active membranes, which exploits the massively parallel nature of the P systems computations by using a massively parallel computer architecture, such as Compute Unified Device Architecture (CUDA) from Nvidia, to obtain better performance in the simulations. We illustrate it by giving a solution to the N-Queens problem as an example.Ponencia On the Power of Insertion P Systems of Small Size(Fénix Editora, 2009) Krassovitskiy, AlexanderIn this article we investigate insertion systems of small size in the framework of P systems. We consider P systems with insertion rules having one symbol context and we show that they have the computational power of matrix grammars. If contexts of length two are permitted, then any recursively enumerable language can be generated. In both cases an inverse morphism and a weak coding were applied to the output of the corresponding P systems.Ponencia Deterministic Solutions to QSAT and Q3SAT by Spiking Neural P Systems with Pre-Computed Resources(Fénix Editora, 2009) Ishdorj, Tseren-Onolt; Leporati, Alberto; Pan, Linqiang; Zeng, Xiangxiang; Zhang, XingyiIn this paper we continue previous studies on the computational effciency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.Ponencia Mutation Based Testing of P Systems(Fénix Editora, 2009) Ipate, Florentin; Gheorgue, MarianAlthough testing is an essential part of software development, until recently, P system testing has been completely neglected. Mutation testing (mutation analysis) is a structural software testing method which involves modifying the program in small ways. Mutation analysis has been largely used in white-box testing, but only a few tentative attempts to use this idea in black-box testing have been reported in the literature. In this paper, we provide a formal way of generating mutants for systems specified by context- free grammars. Furthermore, the paper shows how the proposed method can be used to construct mutants for a P system specification, thus making a significant progress in the area of P system testing