BWMC2006. Brainstorming Week On Membrane Computing (4th. 2006. Sevilla)

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

Examinar

Mostrando 1 - 20 de 34

A Class of P Automata for Characterizing Context-free Languages
(Fénix Editora, 2006) Vaszil, György
We present a characterization of context-free languages in terms of a restricted class of P automata (P systems accepting strings of symbols using symport/antiport communication rules). The characterization is based on the form of the rules used by the system.
The Growth of Branching Structures with P Systems
(Fénix Editora, 2006) Romero Jiménez, Álvaro; 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; Universidad de Sevilla. TIC193: Computación Natural
L-systems have been widely used to model and graphically represent the growth of plants. In, the use of membrane computing for such tasks has been proposed. In this paper we present a di®erent approach, which makes use of the topology of membrane structures to model the morphology of branching structures. We also keep closer to reality by simulating their growth from buds, instead of rewriting existing structures, as L-systems do.
2006 Research Topics in Membrane Computing
(Fénix Editora, 2006) Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIN193: Computación Natural
This is a list of research topics prepared on the occasion of the Fourth Brainstorming Week on Membrane Computing, Sevilla, January 30 - February 3, 2006 (hence the title). The selection is subjective, the presentation is informal (in most cases, the precise formulation of the question to investigate is already part of the research task), the bibliographical information is partial (giving only a starting point for searching the literature; as usual, for a complete bibliography the reader should refer to
Small Universal Spiking Neural P Systems
(Fénix Editora, 2006) Paun, Andrei; Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
In search for small universal computing devices of various types, we consider here the case of spiking neural P systems (SN P systems), in two versions: as devices computing functions and as devices generating sets of numbers. We start with the first case and we produce a universal spiking neural P system with 84 neurons. If a slight generalization of the used rules is adopted, namely, we allow rules for producing simultaneously several spikes, then a considerable improvement, to 49 neurons, is obtained. For SN P systems used as generators of sets of numbers, we find a universal system with restricted rules having 76 neurons, and one with extended rules having 50 neurons.
On an Idea of a (Possibly) Uniform Data Base for Life Sciences from Molecular Biology to Cognitive Psychology
(Fénix Editora, 2006) Obtulowicz, Adam
Reaction Cycles in Membrane Systems and Molecular Dynamics
(Fénix Editora, 2006) Muskulus, Michael; Houweling, Sanne; Rozenberg, Grzegorz; Besozzi, Daniela; Cazzaniga, Paolo; Pescini, Dario; Brijder, Robert
We are considering molecular dynamics and (sequential) membrane systems from the viewpoint of Markov chain theory. The first step is to understand the structure of the configuration space, with respect to communicating classes. Instead of a reachability analysis by traditional methods, we use the explicit monoidal structure of this space with respect to rule applications. This leads to the notion of precycle, which is an element of the integer kernel of the stoichiometric matrix. The generators of the set of precycles can be effectively computed by an incremental algorithm due to Contejean and Devie. To arrive at a characterization of cycles, we introduce the notion of defect, which is a set of geometric constraints on a configuration to allow a precycle to be enabled, that is, be a cycle. An important open problem is the effcient calculation of the defects. We also discuss aspects of asymptotic behavior and connectivity, as well as give a biological example, showing the usefulness of the method for model checking.
Topics and Problems in Metabolic P Systems
(Fénix Editora, 2006) Manca, Vincenzo
P metabolic systems are a special class of P systems which seem to be adequate for expressing biological phenomena related to metabolism and signaling transduction in biological systems. We give the basic motivation for their introduction and some ideas about their applicability and development.
Further Remarks on Trace Languages in P Systems with Symport/Antiport
(Fénix Editora, 2006) Liu, Guangwu; Ionescu, Mihai
P systems are parallel molecular computing models which process multisets of objects in cell-like membrane structures. In this paper we consider the trace languages of a special symbol, the traveler, in symport/antiport P systems where, instead of multisets of objects, sets of objects were considered. Two different ways to define the trace language are proposed. One of the families of languages obtained in this way is proved to be equal to the family of regular languages and the other one to be strictly smaller. Some ideas for further research are also considered.
Three Quantum Algorithms to Solve 3-SAT
(Fénix Editora, 2006) Leporati, Alberto; Felloni, Sara
We propose three quantum algorithms to solve the 3-SAT NP-complete decision problem. The first algorithm builds, for any instance Á of 3-SAT, a quantum Fredkin circuit that computes a superposition of all classical evaluations of Á in a given output line. Similarly, the second and third algorithms compute the same superposition on a given register of a quantum register machine, and as the energy of a given membrane in a quantum P system, respectively. Assuming that a specific non-unitary operator, built using the well known creation and annihilation operators, can be realized as a quantum gate, as an instruction of the quantum register machine, and as a rule of the quantum P system, respectively, we show how to decide whether Á is a positive instance of 3-SAT. The construction relies also upon the assumption that an external observer is able to distinguish, as the result of a measurement, between a null and a non-null vector.
Normal Forms for Spiking Neural P Systems
(Fénix Editora, 2006) Ibarra, Óscar H.; Paun, Andrei; Paun, Gheorghe; Rodríguez Patón, Alfonso; Sosík, Petr; Woodworth, Sara; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
The spiking neural P systems are a class of computing devices recently introduced as a bridge between spiking neural nets and membrane computing. In this paper we prove a series of normal forms for spiking neural P systems, concerning the regular expressions used in the firing rules, the delay between firing and spiking, the forgetting rules used, and the outdegree of the graph of synapses. In all cases, surprising simplifications are found, without losing the computational universality – sometimes at the price of (slightly) increasing other parameters which describe the complexity of these systems.
An Approach to the Degree of Parallelism in P Systems
(Fénix Editora, 2006) 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; Universidad de Sevilla. TIC193: Computación Natural
In the literature, several designs of P systems were used for performing the same task. The use of different techniques or even different P system models makes it very difficult to compare these designs. In this paper, we introduce a new criterion for such a comparison: the degree of parallelism of a P system. To this aim, we define the labeled dependency graph associated with a P system, and we use this new concept for proving some results concerning the maximum number of applications of rules in a single step along the computation of a P system.
Fractals and P Systems
(Fénix Editora, 2006) 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; Universidad de Sevilla. TIC193: Computación Natural
In this paper we show that the massive parallelism, the synchronous appli- cation of the rules, and the discrete nature of their computation, among other features, lead us to consider P systems as natural tools for dealing with fractals. Several examples of fractals encoded by P systems are presented and we wonder about using P systems as a new tool for representing and simulating the fractal nature of tumors.
Small Universal Antiport P Systems and Universal Multiset Grammars
(Fénix Editora, 2006) Freund, Rudolf; Oswald, Marion
Based on the construction of a universal register machine we construct a universal antiport P system working with 31 rules in the maximally parallel mode in one membrane, and a universal antiport P system with forbidden context working with 16 rules in the sequential derivation mode in one membrane for computing any partial recursive function on the set of natural numbers. For accepting/generating any arbitrary recursively enumerable set of natural numbers we need 31/33 and 16/18 rules, respectively. As a consequence of the result for antiport P systems with forbidden context we immediately infer similar results for forbidden random context multiset grammars with arbitrary rules.
Particular Results for Variants of P Systems with One Catalyst in One Membrane
(Fénix Editora, 2006) Freund, Rudolf
Purely catalytic P systems can generate all recursively enumerable sets of natural numbers with only three catalysts in one membrane, whereas we know that one catalyst in one membrane is not enough. On the other hand, P systems also allowing (non-catalytic) non-cooperative evolution rules with only two catalysts in one membrane are already computationally complete, too. We here investigate special variants of P systems with only one catalyst in one membrane that are not computationally complete, i.e., variants of P systems with only one catalyst in one membrane that cannot generate all recursively enumerable sets of natural numbers.
Discrete Solution of Differential Equations by P Metabolic Algorithm
(Fénix Editora, 2006) Fontana, Federico; Manca, Vincenzo
The relationships existing between MP graphs, metabolic P systems, and ODE systems are investigated. Formal results show that every MP system, once derived by its MP graph, results in an ODE system whose solution equals, in the limit, the solution obtained by a non-cooperative MP system that is ODE equivalent to the original one. The freedom of choice of the ODE equivalent from the original MP system resembles the same freedom which is left in the choice and optimization of a numerical scheme while computing the solution of an ODE system.
Solving 3-COL with Tissue P Systems
(Fénix Editora, 2006) Díaz Pernil, Daniel; 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; Universidad de Sevilla. TIC193: Computación Natural
In the literature, several examples of the efficiency of cell-like P systems in order to solve NP-complete problems in polynomial time can be found. Recently, various new models of tissue-like P systems have received important attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem, the 3-COL problem, and discuss the possibilities of tissue-like P systems to solve hard problems.
On the Syntactic Complexity of Darwinian Membrane Systems
(Fénix Editora, 2006) Dassow, Jürgen; Csuhaj Varjú, Erzsébet
Membrane or P systems form a distributed parallel model of computing which is obtained as an abstraction from the structure and functioning of living cells. In this paper we consider a very basic membrane system and add to it checkers which are special finite automata to check whether or not a configuration of the membrane system is "good" or "bad". The computation is only continued if the configuration is good, otherwise it stops without a result. Such membrane systems are called Darwinian P systems. There are three parameters characterizing the size of a system, the number of membranes, the number of checkers, and the size of the checkers measured by the number of states. We prove that we can generate all sets of Parikh vectors of recursively enumerable languages if we restrict the number and size of checkers to one checker with six states or to five checkers with two states. Moreover, we prove that Darwinian systems with one membrane and checkers with at most two states are also sufficient to generate all Parikh sets of recursively enumerable languages. The latter result is optimal since Darwinian systems with checkers with only one state generate only sets of Parikh vectors of ET0L languages. All results are valid for length sets instead of sets of Parikh vectors, too.
Small Computationally Complete Symport/Antiport P Systems
(Fénix Editora, 2006) Csuhaj Varjú, Erzsébet; Margenstern, Maurice; Vaszil, György; Verlan, Sergey
It is known that P systems with symport/antiport rules simulate the register machines, i.e., they are computationally complete. Hence, due to the existence of universal register machines, there exist computationally complete subclasses of symport/antiport P systems with a number of rules limited by a constant. However, there was no estimation of this number in the literature. In this article, we first give a simple estimation of this constant, and then we show that the number can be reduced by grouping together several instructions of the simulated variant of the register machines. Finally, a universal P system with symport/antiport having only 44 rules is obtained.
Spiking Neural P Systems with Extended Rules
(Fénix Editora, 2006) Chen, Haiming; Ishdorj, Tseren-Onolt; 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; Universidad de Sevilla. TIC193: Computación Natural
We consider spiking neural P systems with spiking rules allowed to introduce zero, one, or more spikes at the same time. The computing power of the obtained systems is investigated, when considering them as number generating and as language generating devices. In the first case, a simpler proof of universality is obtained (universality is already known for the restricted rules), while in the latter case we find characterizations of finite and recursively enumerable languages (without using any squeezing mechanism, as it was necessary in the case of restricted rules). The relationships with regular languages are also investigated. In the end of the paper, a tool-kit for computing (some) operations with languages is provided.
Computing Along the Axon
(Fénix Editora, 2006) Chen, Haiming; Ishdorj, Tseren-Onolt; Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
We consider a special form of spiking neural P systems, called axon P sys- tems, corresponding to the activity of Ranvier nodes of neuron axon, and we briefly investigate the language generative power of these devices

Examinar

Envíos recientes