Capítulos (Ciencias de la Computación e Inteligencia Artificial)

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

Examinar

Mostrando 1 - 20 de 73

Specification of Adleman’s Restricted Model Using an Automated Reasoning System: Verification of Lipton’s Experiment
(Springer, 2002) Graciani Díaz, Carmen; Martín Mateos, Francisco Jesús; 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 Cultura (MEC). España; Universidad de Sevilla. TIC193: Computación Natural
The aim ofthis paper is to develop an executable prototype ofan unconventional model ofcomputation. Using the PVS verification system (an interactive environment for writing formal specifications and checking formal proofs), we formalize the restricted model, based on DNA, due to L. Adleman. Also, we design a formal molecular program in this model that solves SAT following Lipton’s ideas.We prove using PVS the soundness and completeness ofthis molecular program. This work is intended to give an approach to the opportunities offered by mechanized analysis ofuncon ventional model ofcomputation in general. This approach opens up new possibilities ofv erifying molecular experiments before implementing them in a laboratory.
Solving Knapsack Problems in a Sticker Based Model
(Springer, 2002) Pérez Jiménez, Mario de Jesús; Sancho Caparrini, Fernando; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
Our main goal in this paper is to give molecular solutions for two NP–complete problems, namely Subset-sum and Knapsack, in a sticker based model for DNA computations. In order to achieve this, we have used a finite set sorting subroutine together with the description of a procedure to formally verify the designed programs through the labeling of test tubes using inductive techniques.
Generation of Diophantine Sets by Computing P Systems with External Output
(Springer, 2002) Romero Jiménez, Álvaro; 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
In this paper a variant of P systems with external output designed to compute functions on natural numbers is presented. These P systems are stable under composition and iteration of functions. We prove that every diophantine set can be generated by such P systems; then, the universality of this model can be deduced from the theorem by Matiyasevich, Robinson, Davis and Putnam in which they establish that every recursively enumerable set is a diophantine set.
A MzScheme Implementation of Transition P Systems
(Springer, 2003) Balbontín Noval, Delia; Pérez Jiménez, Mario de Jesús; Sancho Caparrini, Fernando; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
The main goal of this paper is to present the design of an MzScheme program that allows us to simulate the behavior of transition P systems. For that, a library of procedures have been developed that work in two stages. In the first one, the parsing/compiling stage, the input P system is checked, and if it is well defined, then it is represented by means of an internal grammar. In a second stage, the simulation, the computation tree associated to the P system is generated until a prefixed level.
Hybrid Networks of Evolutionary Processors
(Springer, 2003) Martín Vide, Carlos; Mitrana, Víctor; Pérez Jiménez, Mario de Jesús; 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
A hybrid network of evolutionary processors consists of several processors which are placed in nodes of a virtual graph and can perform one simple operation only on the words existing in that node in accordance with some strategies. Then the words which can pass the output filter of each node navigate simultaneously through the network and enter those nodes whose input filter was passed. We prove that these networks with filters defined by simple random-context conditions, used as language generating devices, are able to generate all linear languages in a very efficient way, as well as non-context-free languages. Then, when using them as computing devices, we present two linear solutions of the Common Algorithmic Problem.
An Agent Based Approach of Collective Foraging
(Springer, 2003) Gheorgue, Marian; Martín Vide, Carlos; Mitrana, Víctor; 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 this paper the behaviour of a bee colony is modeled as a society of communicating agents acting in parallel and synchroniz-ing their behaviour. Two computational models for defining the agents behaviour are introduced and compared and tools developed for these models are briefly illustrated.
Decision P Systems and the P =NP Conjecture
(Springer, 2003) Pérez Jiménez, Mario de Jesús; Romero Jiménez, Álvaro; Sancho Caparrini, Fernando; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Universidad de Sevilla. TIC193: Computación Natural
We introduce decision P systems, which are a class of P systems with symbol-objects and external output. The main result of the paper is the following: if there exists an NP–complete problem that cannot be solved in polynomial time, with respect to the input length, by a deterministic decision P system constructed in polynomial time, then P = NP. From Zandron-Ferreti-Mauri’s theorem it follows that if P = NP, then no NP–complete problem can be solved in polynomial time, with respect to the input length, by a deterministic P system with active membranes but without membrane division, constructed in polynomial time from the input. Together, these results give a characterization of P = NP in terms of deterministic P systems.
The P Versus NP Problem Through Cellular Computing with Membranes
(Springer, 2004) Pérez Jiménez, Mario de Jesús; Romero Jiménez, Álvaro; 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
We study the P versus NP problem through membrane systems. Language accepting P systems are introduced as a framework allowing us to obtain a characterization of the P = NP relation by the polynomial time unsolvability of an NP–complete problem by means of a P system.
Implementing in Prolog an Effective Cellular Solution to the Knapsack Problem
(Springer, 2004) Cordón Franco, Andrés; Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín; 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 an implementation in Prolog of an effective solution to the Knapsack problem via a family of deterministic P systems with active membranes using 2-division.
Computing Partial Recursive Functions by Transition P Systems
(Springer, 2004) Romero Jiménez, Álvaro; 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 this paper a variant of transition P systems with external output designed to compute partial functions on natural numbers is presented. These P systems are stable under composition, iteration and unbounded minimization (μ–recursion) of functions. We prove that every partial recursive function can be computed by such P systems, from which the computational completeness of this model can be deduced.
A Linear-Time Solution to the Knapsack Problem Using P Systems with Active Membranes
(Springer, 2004) 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
Up to now, P systems dealing with numerical problems have been rarely considered in the literature. In this paper we present an effective solution to the Knapsack problem using a family of deterministic P systems with active membranes using 2-division. We show that the number of steps of any computation is of linear order, but polynomial time is required for pre-computing resources.
Accepting Hybrid Networks of Evolutionary Processors
(Springer, 2005) Margenstern, Maurice; Mitrana, Víctor; Pérez Jiménez, Mario de Jesús; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial
We consider time complexity classes defined on accepting hybrid networks of evolutionary processors (AHNEP) similarly to the classical time complexity classes defined on the standard computing model of Turing machine. By definition, AHNEPs are deterministic. We prove that the classical complexity class NP equals the set of languages accepted by AHNEPs in polynomial time.
Attacking the Common Algorithmic Problem by Recognizer P Systems
(Springer, 2005) 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
Many NP-complete problems can be viewed as special cases of the Common Algorithmic Problem (CAP). In a precise sense, which will be defined in the paper, one may say that CAP has a property of local universality. In this paper we present an effective solution to the decision version of the CAP using a family of recognizer P systems with active membranes. The analysis of the solution presented here will be done from the point of view of complexity classes in P systems.
Trading Polarization for Bi-stable Catalysts in P Systems with Active Membranes
(Springer, 2005) 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 the last time, several efforts have been made in order to remove polarizations 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 use bi-stable catalysts. Polarizationless systems with active membranes which use bi-stable catalysts are proven to be computationally complete and able to solve efficiently NP-complete problems. In this paper we present a solution to SAT in linear time. In order to illustrate the presented solution, we also provide a simulation with CLIPS.
On Two-Dimensional Mesh Networks and Their Simulation with P Systems
(Springer, 2005) Ceterchi, Rodica; 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 analize in this paper the possibility of simulating the parallel architecture SIMD-MC2, also known as the two-dimensional mesh, with P systems with dynamic communication graphs. We illustrate this simulation for an algorithm which computes the sum of given integers. Next, we show how to extend the formalism to the reduction problem.
Formal Verification of Programs in Molecular Models with Random Access Memory
(Fénix Editorial, 2005) Pérez Jiménez, Mario de Jesús; Sancho Caparrini, Fernando; Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial; Pérez Jiménez, Mario de Jesús; Romero Jiménez, Álvaro; Sancho Caparrini, Fernando; Ministerio de Ciencia Y Tecnología (MCYT). España; Universidad de Sevilla. TIC193: Computación Natural
Formal verification of molecular programs is a first step towards their automatic processing by means of reasoning systems (ACL2, PVS, etc). In this paper a systematic method to establish verifications of these programs within molecular models with memory, that is, molecular computing models where some operations modifying the inner structure of molecules exist, is proposed. The method presented in this work is applied to relevant problems for the design of molecular programs solving some well-known numerical NP-complete problems: the Generating Cover Families problem, the Set Covering problem and the Minimal Set Cover Selection Problem.
Exploring Computation Trees Associated with P Systems
(Springer, 2005) Cordón Franco, Andrés; 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
Usually, the evolution of a P system generates a computation tree too large to be efficiently handled with present–day computers; moreover, different branches in this tree may differ significantly from a computational complexity point of view, that is, for the amount of time and storage necessary to reach a result. In this paper we propose a first approach to outline a strategy for selecting a suitable branch, in some sense, of the computation tree associated with a P system. To this end, we introduce the key notion of the dependency graph of a P system.
On Descriptive Complexity of P Systems
(Springer, 2005) 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
In this paper we address the problem of describing the complexity of the evolution of a P system. This issue is is specially hard in the case of P systems with active membranes, where the number of steps of a computation is not sufficient to evaluate the complexity. Sevilla carpets were introduced in [1], and they describe the space-time complexity of P systems. Based on them, we define some new parameters which can be used to compare evolutions of P systems. To illustrate this, we also include two different cellular solutions to the Subset Sum problem and compare them via these new parameters.
P Systems with Active Membranes, Without Polarizations and Without Dissolution: A Characterization of P
(Springer, 2005) Gutiérrez Naranjo, Miguel Ángel; Pérez Jiménez, Mario de Jesús; Riscos Núñez, Agustín; 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
We study the computational efficiency of recognizer P systems with active membranes without polarizations and without dissolution. The main result of the paper is the following: the polynomial computational complexity class associated with the class of recognizer P systems is equal to the standard complexity class P.
Using Automated Reasoning Systems on Molecular Computing
(Springer, 2005) Graciani Díaz, Carmen; 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
This paper is focused on the interplay between automated reasoning systems (as theoretical and formal devices to study the correctness of a program) and DNA computing (as practical devices to handle DNA strands to solve classical hard problems with laboratory techniques). To illustrate this work we have proven in the PVS proof checker, the correctness of a program, in a sticker based model for DNA computation, solving the pairwise disjoint families problem. Also we introduce the formalization of the Floyd–Hoare logic for imperative programs.

Examinar

Examinando Capítulos (Ciencias de la Computación e Inteligencia Artificial) por Fecha de publicación