BWMC2007. Brainstorming Week On Membrane Computing (5th. 2007. Sevilla)

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

Examinar

Mostrando 1 - 20 de 20

Fifth Brainstorming Week on Membrane Computing.Sevilla, January 29–February 2, 2007 : RGNC REPORT 01/2007
(Fénix Editora, 2007) Gutiérrez Naranjo, Miguel Ángel; Paun, Gheorghe; Romero Jiménez, Álvaro; 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 Natural
On Two Families of Multiset Tree Automata
(Fénix Editora, 2007) Sempere, José M.; López, Damián
The relation between the membrane structures of P systems and an extension of tree automata which introduces multisets in the transition function has been proposed in previous works. Here we propose two features of tree automata which have been previously studied (namely, reversibility and local testability) in order to extend them to multiset tree automata. The characterization of these families will introduce a new characterization of membrane structures defined by the set of rules used for membrane creation and deletion.
A Software Tool for Dealing with Spiking Neural P Systems
(Fénix Editora, 2007) Ramírez Martínez, Daniel; Gutiérrez Naranjo, Miguel Ángel; 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 Natural
Software simulators for P system are nowadays the main tool to carry out experiments in the eld of Membrane Computing. Although the simulation of a P system is a quite complex task, current simulators have been successfully used for pedagogical purposes and also as assistant tools for researchers. In this paper we present a rst software tool for dealing with Spiking Neural P Systems. This tool outputs the transition diagram of a given system in a step-by-step mode. The code is modular and exible enough to be adapted for further research tasks.
Membrane Computing Schema Based on String Insertions
(Fénix Editora, 2007) Pérez Jiménez, Mario de Jesús; Yokomori, Takashi; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
In this note we introduce the notion of a membrane computing schema for string objects. We propose a computing schema for a membrane network (i.e., tissue-like membrane system) where each membrane performs unique type of operations at a time and sends the result to others connected through the channel. The distinguished features of the computing models obtained from the schema are: 1. only context-free insertion operations are used for string generation, 2. some membranes assume ltering functions for structured objects(molecules), 3. the generating model and accepting model are obtained in the same schema, and both are computationally universal, 4. several known rewriting systems with universal computability can be reformulated in terms of membrane computing schema in a uniform manner. The rst feature provides the model with a simple uniform structure which facilitates a biological implementation of the model, while the second feature suggests further feasibility of the model in terms of DNA complementarity. Through the third and fourth features, one may have a uni ed view of a variety of existing rewriting systems with Turing computability in the framework of membrane computing paradigm.
Twenty Six Research Topics About Spiking Neural P Systems
(Fénix Editora, 2007) Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
Some Mathematical Methods and Tools for an Analysis of Harmony-Seeking Computations
(Fénix Editora, 2007) Obtulowicz, Adam
A general review of some topic concepts and methods of membrane computing, which can be useful in an analysis of harmony-seeking computations is presented. Then an application of a certain particular method of membrane computing in a discussion of mobility of some systems considered in city planning is described in some details. A conclusion of the discussion states that systems of hierarchical organization in a form of a tree are mobile by means of massively parallel (local) moves of the parts of the systems, where the moves are related to the process capabilities of moves of ambients in.
On the Computational Power of Spiking Neural P Systems
(Fénix Editora, 2007) Leporati, Alberto; Zandron, Claudio; Ferretti, Claudio; Mauri, Giancarlo
In this paper we study some computational properties of spiking neural P systems. In particular, we show that by using nondeterminism in a slightly extended version of spiking neural P systems it is possible to solve in constant time both the numerical NP-complete problem Subset Sum and the strongly NP-complete problem 3-SAT. Then, we show how to simulate a universal deterministic spiking neural P system with a deterministic Turing machine, in a time which is polynomial with respect to the execution time of the simulated system. Surprisingly, it turns out that the simulation can be performed in polynomial time with respect to the size of the description of the simulated system only if the regular expressions used in such a system are of a very restricted type.
Several Applications of Spiking Neural P Systems
(Fénix Editora, 2007) Ionescu, Mihai; Sburlan, Dragos
In this paper we investigate some applications of Spiking Neural P Systems regarding their capability to solve some classical computer science problems. In this respect it is studied the versatility of such systems to simulate a well known parallel computational model, namely the Boolean circuits. In addition, another notorious application - the sorting - is considered within this framework.
P Systems with Adjoining Controlled Communication Rules
(Fénix Editora, 2007) Ionescu, Mihai; Sburlan, Dragos
This paper proposes a new model of P systems where the rules are activated by objects present in the neighboring regions. We obtain the computational completeness considering only two membranes, external inhibitors and carriers. Leaving the carriers apart we obtain equality with ET0L systems in terms of number sets.
A Membrane Computing Model for Ballistic Depositions
(Fénix Editora, 2007) Graciani Díaz, Carmen; 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 Natural
Ballistic Deposition was proposed by Vold and Sutherland as a model for colloidal aggregation. These early works were later extended to simulate the process of vapor deposition. In general, Ballistic Deposition models involve (d + 1)-dimensional particles which rain down sequentially at random onto a d-dimensional substrate; when a particle arrives on the existing agglomeration of deposited particles, it sticks to the rst particle it contacts, which may result in lateral growth. In this paper we present a rst P system model for Ballistic Deposition with d = 1.
Spiking Neural P Systems: Stronger Normal Forms
(Fénix Editora, 2007) García Arnau, Marc; Pérez, David; Rodríguez Patón, Alfonso; Sosík, Petr
Spiking neural P systems are computing devices recently introduced as a bridge between spiking neural nets and membrane computing. Thanks to the rapid research in this eld there exists already a series of both theoretical and application studies. In this paper we focus on normal forms of these systems while preserving their computational power. We study combinations of existing normal forms, showing that certain groups of them can be combined without loss of computational power, thus answering partially open problems stated in. We also extend some of the already known normal forms for spiking neural P systems considering determinism and strong acceptance condition. Normal forms can speed-up development and simplify future proofs in this area.
Polarizationless P Systems with Active Membranes Working in the Minimally Parallel Mode
(Fénix Editora, 2007) Freund, Rudolf; Paun, Gheorghe; 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 Natural
We investigate the computing power and the efficiency of P systems with active membranes without polarizations, working in the minimally parallel mode. We prove that such systems are computationally complete and able to solve NP-complete problems even when the rules are of a restricted form, e.g., for establishing computational completeness we only need rules handling single objects and no division of non-elementary membranes is used
A Linear Solution for Subset Sum Problem with Tissue P Systems with Cell Division
(Fénix Editora, 2007) 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 Natural
Tissue P systems are a computing model in the framework of Membrane Computing where the tree-like membrane structure is replaced by a general graph. Recently, it has been shown that endowing these P systems with cell division, NP-complete problems can be solved in polynomial time. In this paper we present a solution to the Subset Sum problem via a family of such devices, and we also include the formal verification of such solution. This is the first solution to a numerical NP-complete problem by using tissue P systems with cell division.
Towards a Causal Semantics for Brane Calculi
(Fénix Editora, 2007) Busi, Nadia
Brane Calculi are a family of biologically inspired process calculi, proposed in [6] to model the interactions of dynamically nested membranes. We propose a semantics that describes the causal dependencies occurring between the reactions of a system described in Brane Calculi. We investigate the basic properties that are satisfied by such a semantics. The notion of causality turns out to be quite relevant for biological systems, as it permits to point out which events occurring in a biological pathway are necessary for another event to happen.
VisualTissue: A Friendly Tool to Study Tissue P Systems Solutions for Graph Problems
(Fénix Editora, 2007) Borrego Ropero, Rafael; Díaz Pernil, Daniel; Nepomuceno Chamorro, Juan Antonio; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
P systems can be classi ed in two main groups: P systems with the membrane structure described by a tree, and tissue P systems with the membranes placed in the nodes of an arbitrary graph. NP-complete problems have been solved in linear time by trading space for time in the framework of recognizing tissue P systems with cell division. The design of this kind of systems is not an easy task to understand. In this paper we present a software application to help the design of solutions to NP-complete problems in the framework of recognizing tissue P systems with cell division.
Information Theory over Multisets
(Fénix Editora, 2007) Bonchis, Cosmin; Izbasa, Cornel; Ciobanu, Gabriel; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
Starting from Shannon theory of information, we present the case of producing information in the form of multisets, and encoding information using multisets. We compute the entropy of a multiset information source by constructing an equientropic string source (with interdependent symbols), and we compare this with a string information source with independent symbols. We then study the encoder and channel part of the system, obtaining some results about multiset encoding length and channel capacity.
Extended Spiking Neural P systems with Excitatory and Inhibitory Astrocytes
(Fénix Editora, 2007) Binder, Aneta; Freund, Rudolf; Oswald, Marion; Vock, Lorenz
We investigate an extended model of spiking neural P systems incorporating astrocytes and their excitatory or inhibitory influence on axons between neurons. Using very restricted variants of extended spiking neural P systems with excitatory and inhibitory astrocytes we can easily model Boolean gates like NAND-gates as well as discrete amplifiers.
Networks of Cells and Petri Nets
(Fénix Editora, 2007) Bernardini, Francesco; Gheorgue, Marian; Margenstern, Maurice; Verlan, Sergey
We introduce a new class of P systems, called networks of cells, with rules allowing several cells to simultaneously interact with each other in order to produce some new objects inside some other output cells. We define different types of behavior for networks of cells by considering alternative strategies for the application of the rules: sequential application, free parallelism, maximal parallelism, locally-maximal parallelism and minimal parallelism. We devise a way for translating network of cells into place- transition nets with localities (PTL-nets, for short) - a specific class of Petri nets. Then, for such a construction, we show a behavioral equivalence between network of cells and corresponding PTL-nets only in the case maximal parallelism, sequential execution, and free parallelism, whereas we observe that, in the case of locally-maximal parallelism and minimal parallelism, the corresponding PTL-nets are not always able to mimic the behavior of network of cells. Also, we address the reverse problem of finding a corresponding network of cells for a given PTL-net by obtaining similar results concerning the relation- ships between their semantics. Finally, we present network-of-cells-based models of two classical synchronization problems: producer/consumer and dining philosophers.
Magnetotactic Bacteria and Their Significance for P Systems and Nanoactuators
(Fénix Editora, 2007) Ardelean, Ioan I.; Ignat, Mircea; Moisescu, Cristina
In the framework of the dialog between P systems and Microbiology, in this paper we focus on the magnetotactic behavior of magnetotactic bacteria, namely the orientation along the Earth’s geomagnetic field lines. Magnetic properties and magnetotactic behavior could be used to obtained micro- and nanoactuators for the desired distribution at nanometer level of either intact magnetotactic bacteria or isolated intact magnetosomes with significant potential application in the construction of magnetic logic gates. Furthermore, (precise) distribution of intact magnetotactic bacteria or isolated intact magnetosomes by carefully using rather strong external magnetic fields could be described by P systems as a discontinuous process, whose potential for nanoactuators and magnetic microchips is increasing in evidence.
Partial Versus Total Halting in P Systems
(Fénix Editora, 2007) Alhazov, Artiom; Freund, Rudolf; Oswald, Marion; Verlan, Sergey
We consider a new variant of the halting condition in P systems, i.e., a computation in a P system is already called halting if not for all membranes a rule is applicable anymore at the same time, whereas usually a computation is called halting if no rule is applicable anymore in the whole system. This new variant of partial halting is especially investigated for several variants of P systems working in different derivation modes.

Examinar

Envíos recientes