BWMC2004. Brainstorming Week On Membrane Computing (2nd. 2004. Sevilla)

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

Examinar

Mostrando 1 - 20 de 39

Covering Rules in P Systems: Some Preliminary Ideas
(Fénix Editora, 2004) Sempere, José M.; Universidad de Sevilla. TIC193: Computación Natural
In this paper we propose a new kind of rules inside the regions of a P system. We have called them covering rules due to the fact that, if selected, they can manage all the objects of the region in an exhaustive manner (i.e., they cover all the objects of the region). First, we propose the formal definition of the rules and different ways of using them. This will introduce a second degree of nondeterminism in the complete behavior of a given P system. We will introduce an effective way to reduce the nondeterminism by defining indexed covering rules. Finally, we will initiate a study of several language families characterized in terms of the covering rules language families.
A Note on Complexity Measures for Probabilistic P Systems
(Fénix Editora, 2004) Sancho Caparrini, Fernando; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
In this paper we present a first approach to the definition of different entropy measures for probabilistic P systems in order to obtain some quantitative parameters showing how complex the evolution of a P system is. To achieve this, we define two possible measures, the first one to reflect the entropy of the P system considered as the state space of possible computations, and the second one to reflect the change of the P system as it evolves.
Simulation of Mobile Ambients by P Systems. Part 2
(Fénix Editora, 2004) Rogozhin, Vladimir; Boian, Elena
Ambient calculus is a theory which deals with mobile computing and computation and encompasses such notions as mobile agents, the ambients where the agents interact and the mobility of the ambients themselves. P systems is a formalism which abstracts from the structure and functioning of living cells and describes distributed parallel computing devices with multiset of objects processing. Ambient calculus and membrane computing are based on the same concepts and structures though they are developed in di®erent areas of computer science. The purpose of our work now is to express ambient calculus by means of P systems, namely by tissue P systems with dynamic network of membranes.
Solving the BINPACKING Problem by Recognizer P Systems with Active Membranes
(Fénix Editora, 2004) Pérez Jiménez, Mario de Jesús; Romero Campero, Francisco José; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
In this paper we present an e®ective solution to the BINPACKING problem using a family of recognizer P systems with active membranes, input membrane and external output. The analysis of the solution presented here will be done form the point of view of complexity classes.
A CLIPS Simulator for Recognizer P Systems with Active Membranes
(Fénix Editora, 2004) Pérez Jiménez, Mario de Jesús; Romero Campero, Francisco José; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
In this paper we propose a new way to represent recognizer P systems with active membranes based on Production Systems techniques. This representation allows us to express the set of rules and the configurations in each step of the evolution as facts in a knowledge base. We provide a CLIPS program to simulate the evolutions of this variant of P systems.
Tissue P Systems with Cell Division
(Fénix Editora, 2004) Paun, Gheorghe; 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 Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
In tissue P systems several cells (elementary membranes) commu- nicate through symport/antiport rules, thus carrying out a computation. We add to such systems the basic feature of (cell) P systems with active membranes { the possibility to divide cells. As expected (as it is the case for P systems with active membranes), in this way we get the possibility to solve computa- tionally hard problems in polynomial time; we illustrate this possibility with SAT problem.
P Systems with Tables of Rules
(Fénix Editora, 2004) Paun, Gheorghe; 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 Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
In the last time, several e®orts were made in order to remove the polarization of membranes from P systems with active membranes; the present paper is a contribution in this respect. In order to compensate the loss of power represented by avoiding polarizations, we introduce tables of rules: each membrane has associated several sets of rules, one of which is non- deterministically chosen in each computation step. Three universality results for tabled P systems are given, trying to use rules of as few as possible types. Then, we consider tables with obligatory rules { rules which must be applied at least once when the table is applied. Systems which use tables with at most one obligatory rule are proven to be able to solve SAT problem in linear time. Several open problems are also formulated.
Further Open Problems in Membrane Computing
(Fénix Editora, 2004) Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
A series of open problems and research topics in membrane com- puting are pointed out, most of them suggested by recent developments in this area. Many of these problems have several facets and branchings, and further facets and branchings can surely be found after addressing them in a more careful manner.
Solving Multidimensional 0-1 Knapsack Problem by P Systems with Input and Active Membranes
(Fénix Editora, 2004) Pan, Linqiang; Martín Vide, Carlos
P systems are parallel molecular computing models based on pro- cessing multisets of objects in cell-like membrane structures. In this paper we give a membrane algorithm to multidimensional 0-1 knapsack problem in lin- ear time by recognizer P systems with input and with active membranes using 2-division. This algorithm can also be modi¯ed to solve general 0-1 integer programming problem.
P Systems with Active Membranes and Separation Rules
(Fénix Editora, 2004) Pan, Linqiang; Ishdorj, Tseren-Onolt
The P systems are a class of distributed parallel computing devices of a biochemical type. In this paper, a new de¯nition of separation rules in P systems with active membranes is given. Under the new de¯nition, the e±ciency and universality of P systems with active membranes and separation rules instead of division are investigated.
Further Remarks on P Systems with Active Membranes, Separation, Merging, and Release Rules
(Fénix Editora, 2004) Pan, Linqiang; Alhazov, Artiom; Ishdorj, Tseren-Onolt
The P systems are a class of distributed parallel computing devices of a biochemical type. In this note, we show that by using membrane separation to obtain exponential workspace, SAT problem can be solved in linear time in a uniform and con°uent way by active P systems without polarizations. This improves some results already obtained by A. Alhazov, Ts. Ishdorj. A universality result related to membrane separation is also obtained.
A Java Simulator for Basic Transition P Systems
(Fénix Editora, 2004) Nepomuceno Chamorro, Isabel de los Ángeles; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
In this paper, a software tool (called SimCM, from Spanish Sim- ulador de Computaci¶on con Membranas) for handling P systems is presented. The program can simulate basic transition P Systems where dissolution of membranes and priority rules are allowed. This is a ¯rst step to cross the border between simulations and distributed implementations that capture the parallelism existing in this model.
Simulating the Fredkin Gate with Energy-Based P Systems
(Fénix Editora, 2004) Leporati, Alberto; Zandron, Claudio; Mauri, Giancarlo
Reversibility plays a fundamental role when the possibility to per- form computations with minimal energy dissipation is considered. Many pa- pers on reversible computation have appeared in literature: the most famous are certainly the work of Bennett on (universal) reversible Turing machines and the work of Fredkin and To®oli on conservative logic. The latter is based upon the Fredkin gate, a reversible and \conservative" (according to a de¯nition given by Fredkin and To®oli) three{input/three{output boolean gate. In this paper we introduce energy{based P systems as a parallel and distributed model of computation in which the amount of energy manipulated and/or consumed during computations is taken into account. Moreover, we show how energy{based P systems can be used to simulate the Fredkin gate. The proposed P systems that perform the simulation turn out to be themselves reversible and conservative.
A Tissue P System and a DNA Microfluidic Device for Solving the Shortest Common Superstring Problem
(Fénix Editora, 2004) Ledesma, Lucas; Manrique, Daniel; Rodríguez Patón, Alfonso; Silva, Andrés
This paper describes a tissue P system for solving the Shortest Common Superstring Problem in linear time. This tissue P system is well suited for parallel and distributed implementation using a micro°uidic device working with DNA strands. The tP system is not based on the usual brute force generate/test technique applied in DNA computing, but builds the space solution gradually. The possible solutions/superstrings are build step by step through the parallel distributed combination of strings using the overlapping concatenation operation. Moreover, the DNA micro°uidic device solves the problem autonomously, without the need of external control or manipulation.
On P Systems with Promoters/Inhibitors
(Fénix Editora, 2004) Ionescu, Mihai; Sburlan, Dragos
This article shows how the computational universality can be reached by using P systems with object rewriting context-free rules, promot- ers/inhibitors and one catalyst. Both generative and accepting cases are stud- ied. Some examples that illustrate the theoretical issues are also presented.
Deductive Databases and P Systems
(Fénix Editora, 2004) Gutiérrez Naranjo, Miguel Ángel; Rogozhin, Vladimir; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Ministerio de Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
In computational processes based on backwards chaining, a rule of the type A Ã B1; : : : ;Bn is seen as a procedure which points that the problem A can be split into the problems B1; : : : ;Bn. In classical devices, the subproblems B1; : : : ;Bn are solved sequentially. In this paper we present some questions that circulated during the Second Brainstorming Week related to the application of the parallelism of P systems to computation based on backwards chaining, and we illustrate them with the example of inferential deductive process.
Towards a Programming Language in Cellular Computing
(Fénix Editora, 2004) 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 Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
Several solutions to hard numerical problems using P systems have been presented recently, and strong similarities in their designs have been no- ticed. In this paper we present a new solution, an e®ective one to the Partition problem via a family of deterministic P systems with active membranes using 2-division. We intend to show that the idea of a cellular programming lan- guage is possible, indicating some \subroutines" that can be used in a variety of situations and therefore could be useful for attacking new problems in the future.
An Efficient Cellular Solution for the Partition Problem
(Fénix Editora, 2004) 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 Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
Numerical problems are not very frequently addressed in the P sys- tems literature. In this paper we present an e®ective solution to the Partition problem via a family of deterministic P systems with active membranes using 2-division. The design of this solution is a sequel of several previous works on other problems, mainly the Subset-Sum and the Knapsack problems but also the VALIDITY and SAT. Several improvements are introduced and explained.
About P Systems with Symport/Antiport
(Fénix Editora, 2004) Frisco, Pierluigi
It is proved that four membranes su±ce to P systems with minimal symport/antiport to generate all recursively enumerable sets of numbers. It is also proved that P systems with symport/antiport without maximal par- allelism are equivalent to partially blind counter automata.
Tissue-like P Systems with Channel-States
(Fénix Editora, 2004) 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; Universidad de Sevilla. TIC193: Computación Natural
We consider tissue-like P systems with states associated with the links (we call them synapses) between cells, controlling the passage of objects across the links. We investigate the computing power of such devices for the case of using - in a sequential manner - antiport rules of small weights. Sys- tems with two cells are proven to be universal when having arbitrarily many states and minimal antiport rules, or two states, and antiport rules of weight two. Also the systems with arbitrarily many cells, three states, and minimal antiport rules are universal. In contrast, the systems with one cell and any number of states and rules of any weight only compute Parikh sets of ma- trix languages (generated by matrix grammars without appearance checking); characterizations of Parikh images of matrix languages are obtained for such one-cell systems with antiport rules of a reduced weight. A series of open problems are also formulated.

Examinar

Envíos recientes