BWMC2008. Brainstorming Week On Membrane Computing (6th. 2008. Sevilla)
URI permanente para esta colecciónhttps://hdl.handle.net/11441/34357
Examinar
Envíos recientes
Libro Sixth Brainstorming Week on Membrane Computing Sevilla, February 4–February 8, 2008 : RGNC REPORT 01/2008(Fénix Editora, 2008) Díaz Pernil, Daniel; Graciani Díaz, Carmen; 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 NaturalPonencia A Quantum-Inspired Evolutionary Algorithm Based on P systems for a Class of Combinatorial Optimization(Fénix Editora, 2008) Zhang, Gexiang; Gheorgue, Marian; Wu, ChaozhongThis paper introduces an evolutionary algorithm which uses the concepts and principles of the quantum-inspired evolutionary approach and the hierarchical arrangement of the compartments of a P system. The P system framework is also used to formally specify this evolutionary algorithm. Extensive experiments are conducted on a well-known combinatorial optimization problem, the knapsack problem, to test the effectiveness of the approach. These experimental results show that this evolutionary algorithm performs better than quantum-inspired evolutionary algorithms, for certain arrangements of the compartments of the P system structure utilized.Ponencia On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution(Fénix Editora, 2008) Zandron, Claudio; Leporati, Alberto; Ferretti, Claudio; Mauri, Giancarlo; 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 NaturalRecognizer P systems with active membranes have proven to be very powerful computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-sat by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximal parallel way.Ponencia Computing by Carving with P Systems. A First Approach(Fénix Editora, 2008) Sempere, José M.In this work, we propose a P system which carries out computing by carving. Computing by carving was proposed by Gh. P˘aun as a technique to generate formal languages which can even be non recursively enumerable. Hence, it can be considered a hypercomputational technique. Here, we propose a first scheme based on P systems in order to perform computing by carving any formal language. So, the paper shows indirectly that these systems, under certain assumptions, can be considered a model for hypercomputation.Ponencia Graphics and P Systems: Experiments with JPLANT(Fénix Editora, 2008) Rivero Gil, Elena; Gutiérrez Naranjo, Miguel Ángel; 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 hand-made graphical representation of the configuration of a P system becomes a hard task when the number of membranes and objects increases. In this paper we present a new software tool, called JPLANT, for computing and representing the evolution of a P system model with membrane creation.We also present some experiments performed with JPLANT and point out new lines for the research in computer graphics with membrane systems.Ponencia Ordinary Membrane Machines versus Other Mathematical Models of Systems Realizing Massively Parallel Computations(Fénix Editora, 2008) Obtulowicz, AdamA comparison of ordinary membrane machines, understood as certain recursive families of deterministic P systems, with some other mathematical models of systems realizing massively parallel computations is discussed. These mathematical models are those which respect recursiveness of computational tasks of systems, i.e., the functions to be computed are recursive functions and the decision problems correspond to recursive sets. The comparison together with open problems is summarized in the enclosed tables, where open problems are indicated by question mark “?”.Ponencia A First Model for Hebbian Learning with Spiking Neural P Systems(Fénix Editora, 2008) Gutiérrez Naranjo, Miguel Ángel; 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 NaturalSpiking neural P systems and artificial neural networks are computational devices which share a biological inspiration based on the transmission of information among neurons. In this paper we present a first model for Hebbian learning in the framework of Spiking Neural P systems by using concepts borrowed from neuroscience and artificial neural network theory.Ponencia Solving Numerical NP-complete Problems by Spiking Neural P Systems with Pre–computed Resources(Fénix Editora, 2008) Gutiérrez Naranjo, Miguel Ángel; Leporati, Alberto; 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 NaturalRecently we have considered the possibility of using spiking neural P systems for solving computationally hard problems, under the assumption that some (possibly exponentially large) pre-computed resources are given in advance. In this paper we continue this research line, and we investigate the possibility of solving numerical NP-complete problems such as Subset Sum. In particular, we first propose a semi–uniform family of spiking neural P systems in which every system solves a specified instance of Subset Sum. Then, we exploit a technique used to calculate Iterated Addition with boolean circuits to obtain a uniform family of spiking neural P systems in which every system is able to solve all the instances of Subset Sum of a fixed size. All the systems here considered are deterministic, but their size generally grows exponentially with respect to the instance size.Ponencia Research Topics Arising from the (Planned) P Systems Implementation Experiment in Technion(Fénix Editora, 2008) Gershoni, Renana; Keinan, Ehud; Paun, Gheorghe; Piran, Ron; Ratner, Tamar; Shoshani, Sivan; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación NaturalWe formulate here a few technical (mathematical) open problems related to the in vitro bio-chemical experiment planned in Technion for computing the Fibonacci sequence in terms of P systems. So-called local-loop-free P systems are introduced and their universality for various types of P systems as well as other issues are mentioned as research questions.Ponencia Testing Einstein’s Formula on Brownian Motion Using Membrane Computing(Fénix Editora, 2008) Gálvez Santisteban, Manuel A.; Gutiérrez Naranjo, Miguel Ángel; Ramírez Martínez, Daniel; Rivero Gil, Elena; 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 NaturalBrownian motion refers to erratic movements of small particles of solid matter suspended in a fluid and it is the basis of the development of many fractals found in Nature. In this paper we use the Membrane Computing model of P systems with membrane creation and the software tool JPLANT in order to check the Einstein’s theory on the Mean Square Displacement of Brownian motion.Ponencia No Cycles in Compartments. Starting from Conformon-P Systems(Fénix Editora, 2008) Frisco, Pierluigi; Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación NaturalStarting from proofs of results about the computing power of conformon- P systems, we infer several results about the power of certain classes of tissue-like P systems with (cooperative) rewriting rules used in an asynchronous way, without cycles in compartments. This last feature is related to an important restriction appearing when dealing with lab implementations of P systems, that of avoiding local evolution loops of objects.Ponencia P-Lingua: A Programming Language for Membrane Computing(Fénix Editora, 2008) Díaz Pernil, Daniel; Pérez Hurtado de Mendoza, Ignacio; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín; 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 has already been addressed, yielding a first generation of applications. In this paper, we develop a new programming language: P-Lingua. Furthermore, we present a simulator for the class of recognizing P systems with active membranes. We illustrate it by giving a solution to the SAT problem as an example.Ponencia Solving the Partition Problem by Using Tissue-like P Systems with Cell Division(Fénix Editora, 2008) Díaz Pernil, Daniel; Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín; 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 NaturalTissue-like P systems with cell division is a computing model in the framework of Membrane Computing that shares with the spiking neural P system model a similar biological inspiration. Namely, both models are based on the intercellular communication and cooperation between neurons, respectively. Due to this fact, in both models the devices have the same structure: a network of elementary units (cells in a tissue and interconnected neurons, respectively). Nonetheless, the two models are quite different. One of the differences is the ability of tissue-like P systems with cell division for increasing the number of cells during the computation. In this paper we exploit this ability and present a polynomial-time solution for the (NP-complete) Partition problem via a uniform family of such P systems.Ponencia Computational Complexity of Simple P Systems(Fénix Editora, 2008) Ciobanu, Gabriel; Resios, AndreasWe introduce a new class of membrane systems called simple P systems, and study its computational complexity using the classical theory. We start by presenting the knapsack problem and analyzing its space and time complexities. Then we study the computational complexity of simple P systems by considering the static allocation of resources enabling the parallel application of the rules. We show that the problem of allocating resources for simple P systems is NP-complete by reducing it to the knapsack problem. Thus we express the computational complexity of this class of P systems in terms of classical complexity theory.Ponencia Spiking Neural P Systems – A Natural Model for Sorting Networks(Fénix Editora, 2008) Ceterchi, Rodica; Tomescu, Alexandru IoanThis paper proposes two simulations of sorting networks with spiking neural P systems. A comparison between different models is also made.Ponencia Sorting Omega Networks Simulated with P Systems: Optimal Data Layouts(Fénix Editora, 2008) Ceterchi, Rodica; Pérez Jiménez, Mario de Jesús; Tomescu, Alexandru Ioan; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación NaturalThe paper introduces some sorting networks and their simulation with P systems, in which each processor/membrane can hold more than one piece of data, and perform operations on them internally. Several data layouts are discussed in this context, and an optimal one is proposed, together with its implementation as a P system with dynamic communication graphs.Ponencia On Modeling Signal Transduction Networks(Fénix Editora, 2008) Castellini, Alberto; Franco, GiudittaSignal transduction networks are very complex processes employed by the living cell to suitably react to environmental stimuli. Qualitative and quantitative computational models play an increasingly important role in the representation of these networks and in the search of new insights about these phenomena. In this work we analyze some graph-based models used to discover qualitative properties of such networks. In turn, we show that MP systems can naturally extend these graph-based models by adding some qualitative elements. The case study of integrins activation during the lymphocyte recruitment, a crucial phenomenon in inflammatory processes, is described, and a first MP graph for this network is designed. Finally, we discuss some open problems related to the qualitative modeling of signaling networks.Ponencia A P System Modeling an Ecosystem Related to the Bearded Vulture(Fénix Editora, 2008) Cardona, Mónica; Colomer, M. Angels; Pérez Jiménez, Mario de Jesús; Sanuy, Delfí; Margalida, Antoni; 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 Bearded Vulture is one of the rarest raptors in Europe and it is an endangered species. In this paper, we present a model of an ecosystem related with the Bearded Vulture which is located in the Catalan Pyrenees, by using P systems. The population dynamics constituted by the Bearded Vulture (that feeds almost exclusively on bones) and other five subfamilies that provide the bones they feed on, is studied. P systems provide a high level computational modeling framework which integrates the structural and dynamical aspects of ecosystems in a comprehensive and relevant way. P systems explicitly represent the discrete character of the components of an ecosystem by using rewriting rules on multisets of objects which represent individuals of the population and bones. The inherent stochasticity and uncertainty in ecosystems is captured by using probabilistic strategies. In order to give an experimental validation of the P system designed, we have constructed a simulator that allows us to analyze the evolution of the ecosystem with different initial conditions.Ponencia (Tissue) P Systems Using Non-cooperative Rules Without Halting Conditions(Fénix Editora, 2008) Beyreder, Markus; Freund, RudolfWe consider (tissue) P systems using non-cooperative rules, but considering computations without halting conditions. As results of a computation we take the contents of a specified output membrane/cell in each derivation step, no matter whether this computation will ever halt or not, eventually taking only results completely consisting of terminal objects only. The computational power of (tissue) P systems using non-cooperative rules turns out to be equivalent to that of (E)0L systems.Ponencia Towards a P Systems Normal Form Preserving Step-by-step Behavior(Fénix Editora, 2008) Barbuti, Roberto; Maggiolo Schettini, Andrea; Milazzo, Paolo; Tini, SimoneStarting from a compositional operational semantics of transition P Systems we have previously defined, we face the problem of developing an axiomatization that is sound and complete with respect to some behavioural equivalence. To achieve this goal, we propose to transform the systems into a unique normal form which preserves the semantics. As a first step, we introduce axioms which allow the transformation of mem- brane structures with no dissolving rules into flat membranes. We discuss the problems which arise when dissolving rules are allowed and we suggest possible solutions. We leave as future work the further step that leads to the wanted normal form.