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

Handling Markov Chains with Membrane Computing
(Fénix Editora, 2006) Cardona, Mónica; Colomer, M. Angels; Pérez Jiménez, Mario de Jesús; Zaragoza, Alba; 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 approach the problem of computing the n–th power of the transition matrix of an arbitrary Markov chain through membrane computing. The proposed solution is described in a semi–uniform way in the framework of P systems with external output. The amount of resources required in the construction is polynomial in the number of states of the Markov chain and in the power. The time of execution is linear in the power and is independent of the number of states involved in the Markov chain.
On an Idea of a (Possibly) Uniform Data Base for Life Sciences from Molecular Biology to Cognitive Psychology
(Fénix Editora, 2006) Obtulowicz, Adam
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.
Multiset Random Context Grammars, Checkers, and Transducers
(Fénix Editora, 2006) Cavaliere, Matteo; Freund, Rudolf; Oswald, Marion; Sburlan, Dragos
We introduce a general model of random context multiset grammars as well as the concept of multiset random context checkers and transducers. Our main results show how recursively enumerable sets of finite multisets can be generated using these models of computing; corresponding results for antiport P systems are established, too.
On String Languages Generated by Spiking Neural P Systems
(Fénix Editora, 2006) Chen, Haiming; Freund, Rudolf; Ionescu, Mihai; 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 continue the study of spiking neural P systems by considering these computing devices as binary string generators: the set of spike trains of halting computations of a given system constitutes the language generated by that system. Although the work of spiking neural P systems is rather restricted (and this is illustrated by the fact that very simple languages cannot be generated in this framework), regular languages are inverse-morphic images of languages of finite spiking neural P systems, and recursively enumerable languages are projections of inverse-morphic images of languages generated by spiking neural P systems.
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
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.
Uniform Solution to QSAT Using Polarizationless Active Membranes
(Fénix Editora, 2006) Alhazov, Artiom; 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
It is known that the satisfiability problem (SAT) can be solved a semi- uniform family of deterministic polarizationless P systems with active membranes with non-elementary membrane division. We present a double improvement of this result by showing that the satisfiability of a quantified boolean formula (QSAT) can be solved by a uniform family of P systems of the same kind.
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.
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.
Two Universality Results for (Mem)Brane Systems
(Fénix Editora, 2006) Besozzi, Daniela; Busi, Nadia; Franco, Giuditta; Freund, Rudolf; Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
We prove that P systems with mate and drip operations and using at most five membranes during any step of a computation are universal. This improves a recent similar result from, where eleven membranes are used. The proof of this result has the "drawback" that the output of a computation is obtained on an inner membrane of the system. A universality proof is then given for the case when the result of a computation is found on the skin membrane (on its external side, hence "visible" from the environment), but in this case we use one more membrane, as well as another basic brane operation exo; moreover, the operations are now of the projective type, as introduced in.
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.
Some Notes on the Interplay Between P Systems and Chemotaxis in Bacteria
(Fénix Editora, 2006) Ardelean, Ioan I.; Besozzi, Daniela
We describe some chemotactic behaviors of bacteria, that is, their movement response to changes in the environment, and the underlying molecular mechanisms. We outline how such processes could be linked to membrane computing, by taking inspiration from them for new type of rules or new features to be introduced in P systems, as well as by considering how the application of recent P system-based models can produce relevant results for the description and the analysis of chemotaxis processes.
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.
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.
Rewriting in P Systems: An Algebraic Approach
(Fénix Editora, 2006) Ceterchi, Rodica
We reformulate in algebraic terms the maximal parallel rewriting of symbols which occur inside membranes of a P 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.
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.
On Trace Languages Generated by Spiking Neural P Systems
(Fénix Editora, 2006) Chen, Haiming; Ionescu, Mihai; Paun, Andrei; Paun, Gheorghe; Popa, Bianca; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
We extend to spiking neural P systems a notion investigated in the “stan- dard” membrane systems: the language of the traces of a distinguished object. In our case, we distinguish a spike by “marking” it and we follow its path through the neurons of the system, thus obtaining a language. Several examples are discussed and some preliminary results about this way of associating a language with a spiking neural P system are given, together with a series of topics for further research. For instance, we show that each regular language is the morphic image of a trace language intersected with a very particular regular language, while each recursively enumerable language over the one-letter alphabet is the projection of a trace language.
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.

Examinar

Examinando BWMC2006. Brainstorming Week On Membrane Computing (4th. 2006. Sevilla) por Fecha de publicación