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

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
A Case Study in (Mem)Brane Computation: Generating {n2 | n 1}
(Fénix Editora, 2006) Busi, Nadia; 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; Universidad de Sevilla. TIC193: Computación Natural
The aim of this paper is to start an investigation and a comparison of the expressiveness of the two most relevant formalisms inspired by membranes interactions, namely, P systems and Brane Calculi. We compare the two formalisms w.r.t. their ability to act as language generators. In particular, we show different ways of generating the set L = {n2 | n 1} in P systems and in Brane Calculi.
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.
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.
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
Decidability of Divergence for Catalytic P Systems
(Fénix Editora, 2006) Busi, Nadia
P systems are a biologically inspired model introduced by Gheorghe P¸aun with the aim of representing the structure and the functioning of the cell. Since their introduction, several variants of P systems have been proposed and explored. We concentrate on the class of catalytic P systems without priorities associated to the rules. We show that the divergence problem (i.e., checking for the existence of an infinite computation) is decidable in such a class of P systems. As a corollary, we obtain an alternative proof of the nonuniversality of deterministic catalytic P systems, an open problem recently solved by Ibarra and Yen.
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.
Encodings and Arithmetic Operations in P Systems
(Fénix Editora, 2006) Alhazov, Artiom; Bonchis, Cosmin; Ciobanu, Gabriel; Izbasa, Cornel
Following, we present in this paper various number encodings and operations over multisets. We obtain the most compact encoding and several other interesting encodings and study their properties using elements of combinatorics over multisets. We also construct P systems that implement their associated operations. We quantify the effect of adding order to a multiset thus obtaining a string, as going from encoding lengths of the number n in base b and time complexities of operations of the order b p n to lengths and complexities of order logbn:
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.
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.
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.
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.
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.
On an Idea of a (Possibly) Uniform Data Base for Life Sciences from Molecular Biology to Cognitive Psychology
(Fénix Editora, 2006) Obtulowicz, Adam
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.
On the Efficiency of Spiking Neural P Systems
(2006) Chen, Haiming; Ionescu, Mihai; Ishdorj, Tseren-Onolt; Universidad de Sevilla. TIC193: Computación Natural
Spiking neural P systems were recently introduced in and proved to be Turing complete as number computing devices. In this paper we show that these systems are also computationally efficient. Specifically, we present a variant of spiking neural P systems which have, in their initial configuration, an arbitrarily large number of inactive neurons which can be activated (in an exponential number) in polynomial time. Using this model of P systems we can deterministically solve the satisfiability problem (SAT) in constant time.
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.
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.
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.
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.

Examinar

Examinando BWMC2006. Brainstorming Week On Membrane Computing (4th. 2006. Sevilla) por Título