Informática

URI permanente para esta comunidadhttps://hdl.handle.net/11441/33181

Examinar

Mostrando 1 - 20 de 600

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.
P Systems with Symport/Antiport of Rules
(Fénix Editora, 2004) Cavaliere, Matteo; Genova, Daniela
Moving \instructions" instead of \data", using transport mecha- nisms inspired by biology { this could represent, shortly, the basic idea of the computing device presented in this paper. Speci¯cally, we propose a new class of P systems that use, at the same time, evolution rules and symport/antiport rules. The idea of this kind of systems is simple: during a computation symbol- objects (the \data") evolve using evolution rules but they cannot be moved; on the other hand, the evolution rules (the \instructions") can be moved across the membranes using classical symport/antiport rules. We present di®erent results using di®erent combinations between the power of the evolution rules (catalytic, non-cooperative rules) and the weight of the symport/antiport rules. In particular, we show that, using non-cooperative rules and antiports of un- bounded weight is possible to obtain at least the Parikh set of ET0L languages. On the other hand, using catalytic rules (one catalyst) and antiports of weight 2, the system becomes universal. Several open problems are also presented.
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.
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.
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.
Computing Using Signals: From Cells to P Systems
(Fénix Editora, 2004) Ardelean, Ioan I.; Cavaliere, Matteo; Sburlan, Dragos
In cell biology one of the fundamental topic is the study of how biological signals are managed by cells. Signals can arise from inside the cell or from the external environment and the correct answer to certain signals is essential for bacteria to survive in a certain environment. Starting from these biological motivations we consider a model of P systems where the computa- tion is controlled by signals which move across the regions. In particular, we consider Signals-Based P systems where the symbol-objects cannot be moved and the rules can be activated/inactivated using a ¯nite number of signals (signal-promoters) moved across the membranes; di®erently from standard P systems using promoters, in our case promoters cannot be created during the computation. After discussing the biological motivations we show how this model becomes universal when it uses one catalyst, and a bounded number of signal-promoters.
P Systems with Active Membranes and Without Polarizations
(Fénix Editora, 2004) Freund, Rudolf; Paun, Andrei
P systems with active membranes but without using electrical charges (polarizations) are shown to be complete for generating recursively enumerable string languages when working on string objects and using only rules with membrane transitions as well as rules with membrane dissolving and elementary membrane division, but also when using various other kinds of rules, even including a new type of rules allowing for membrane generation. Especially, allowing for changing membrane labels turns out to be a very powerful control feature.
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.
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.
Maximum Search Using P Systems
(Fénix Editora, 2004) Fontana, Federico; Franco, Giuditta
Several algorithms of maximum search are investigated and eval- uated in different types of P systems, namely using priorities, multiple nested membranes and linked transport. The proposed solutions are expected to find application in a wide range of problems. In particular, the authors are currently working on modeling an algorithm for DNA sequence alignment using P systems.
Pumps Systems of Membranes
(Fénix Editora, 2004) Ciobanu, Gabriel
The reactivity of the living cells provides the real complexity of biological systems. This paper presents a reactive P system where the rules are triggered by certain conditions, and pumps are the parallel processors of a membrane. The computation of a reactive P system is given by parallel composition of conditional rules regarding the pumps, and by sequential and parallel composition of internal rules regarding the coordination activity of the membrane nucleus. Starting from this description, it is possible to de¯ne the operational semantics and various behavioural equivalences between mem- branes. Finally, some perspectives and open problems are presented. Overall this approach is a step toward a programming paradigm inspired by membrane activity.
P Systems with Active Membranes and Two Polarizations
(Fénix Editora, 2004) Alhazov, Artiom; Freund, Rudolf; Paun, Gheorghe; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
P systems with active membranes using only two electrical charges and only rules of types (a) and (c) assigned to at most two membranes are shown to be computationally complete { thus improving the previous result of this type from the point of view of the number of polarizations as well as with respect to the number of membranes. Allowing a special variant of rules of type (c) to delete symbols by sending them out, even only one membrane is needed. Moreover, we present an algorithm for deterministically deciding SAT in linear time using only two polarizations and global rules of types (a) ; (c), and (e).
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.
Looking for P Truth
(Fénix Editora, 2004) Cordón Franco, Andrés; 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 Ciencia y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
In a general sense, Logic studies how to derive new pieces of in- formation from previous ones. In this paper we explore the analogies between P systems, where new configurations can be obtained from previous ones by using a set of rules, and the derivation of new theorems from previous ones or from axioms by using inference rules.
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.
(Ultimately Confluent) Parallel Multiset-Rewriting Systems with Context
(Fénix Editora, 2004) Alhazov, Artiom; Sburlan, Dragos
The aim of this paper is to study the power of parallel multiset- rewriting systems with permitting context (or P systems with non-cooperative rules with promoters). The main result obtained is that if we use promoters of weight two, then the system is universal. Moreover, the construction satis¯es a special property we de¯ne: it is ulti- mately con°uent. This means that if the system allows at least one halting computation, then its ¯nal con¯guration is reachable from any reachable con- ¯guration.
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.
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.
Sequential P Systems with Unit Rules and Energy Assigned to Membranes
(Fénix Editora, 2004) Freund, Rudolf; Leporati, Alberto; Oswald, Marion; Zandron, Claudio
We introduce a new variant of membrane systems where the rules are directly assigned to membranes (and not to the regions as this is usually observed in the area of membrane systems) and, moreover, every membrane carries an energy value that can be changed during a computation by objects passing through the membrane. For the application of rules leading from one configuration of the system to the succeeding configuration we consider a sequential model and do not use the model of maximal parallelism. The result of a successful computation is considered to be the distribution of energy values carried by the membranes. We will show that for such systems using a kind of priority relation on the rules we already obtain universal computational power. When omitting the priority relation, we obtain a characterization of the family of Parikh sets generated by context-free matrix grammars (with ¸¡rules).
On the Power of Deterministic EC P Systems
(Fénix Editora, 2004) Alhazov, Artiom
It is commonly believed that a signi¯cant part of the computational power of membrane systems comes from their inherent non-determinism. Re- cently, R. Freund and Gh. P¸aun have considered deterministic P systems, and formulated the general question whether the computing (generative) capacity of non-deterministic P systems is strictly larger than the (recognizing) capacity of their deterministic counterpart. In this paper, we study the computational power of deterministic P systems in the evolution{communication framework. It is known that, in the genera- tive case, two membranes are enough for universality. For the deterministic systems, we obtain the universality with three membranes, leaving the original problem open.

Examinar

Examinando Informática por Fecha de publicación