Catálogo de publicaciones - libros

It is an unconventional computation approach to evolve solutions instead of calculating them. Although using evolutionary computation in computer science dates back to the 1960s, using an evolutionary approach to program other algorithms is not that well known. In this paper a genetic algorithm is used to evolve behavior in cellular automata. It shows how this approach works for different topologies and neighborhood shapes. Some different one dimensional neighborhood shapes are investigated with the genetic algorithm and yield surprisingly good results.

Consider a database most of whose entries are marked but the precise fraction of marked entries is not known. What is known is that the fraction of marked entries is 1–, where is a random variable that is uniformly distributed in the range (0,).The problem is to try to select a marked item from the database in a single query. If the algorithm selects a marked item, it succeeds, else if it selects an unmarked item, it makes an error.

How low can we make the probability of error? The best possible classical algorithm can lower the probability of error to (). The best known quantum algorithms for this problem could also only lower the probability of error to ( ). Using a recently invented quantum search technique, this paper gives an algorithm that reduces the probability of error to (). The algorithm is asymptotically optimal.

Cis-regulatory modules that control developmental gene expression process the regulatory inputs provided by the transcription factors for which they contain specific target sites. A prominent class of cis-regulatory processing functions can be modeled as logic operations. Many of these are combinatorial because they are mediated by multiple sites, although others are unitary. In this work, we illustrate the repertoire of cis-regulatory logic operations, as an approach toward a functional interpretation of the genomic regulatory code.

Structural DNA nanotechnology entails the construction of objects, lattices and devices from branched DNA molecules. Branched DNA molecules open the way for the construction of a variety of N-connected motifs. These motifs can be joined by cohesive interactions to produce larger constructs in a bottom-up approach to nanoconstruction. The first objects produced by this approach were stick polyhedra and topological targets, such as knots and Borromean rings. These were followed by periodic arrays with programmable patterns. It is possible to exploit DNA structural transitions and sequence-specific binding to produce a variety of DNA nanomechanical devices, which include a bipedal walker and a machine that emulates the translational capabilities of the ribosome. Much of the promise of this methodology involves the use of DNA to scaffold other materials, such as biological macromolecules, nanoelectronic components, and polymers. These systems are designed to lead to improvements in crystallography, computation and the production of diverse and exotic materials. Branched DNA can be used to emulate Wang tiles, and it can be used to construct arbitrary irregular graphs and to address their colorability.

The biological world offers a full range of adaptive mechanisms, from which technology researchers try to get inspiration. Among the several disciplines attempting to reproduce these mechanisms artificially, this paper concentrates on the field of Neural Networks and its contributions to attain sensorimotor adaptivity in robots. Essentially this type of adaptivity requires tuning nonlinear mappings on the basis of input-output information. Several experimental robotic systems are described, which rely on inverse kinematics and visuomotor mappings. Finally, the main trends in the evolution of neural computing are highlighted, followed by some remarks drawn from the surveyed robotic applications.

We introduce a model of self-assembly P systems as devices that use some of the features of population P systems to progressively grow a graph structure by forming new bonds between the existing cells and some new cells which are brought into the system step by step. The new cells are then able to self-assemble locally either at the level of cells or at the level of neighbourhoods of cells by using bond-making rules according to a specific self-assembly model. We describe two self-assembly models, called respectively parallel single-point self-assembly and parallel multi-point self-assembly. Then, we precisely state the problem of programmable self-assembly for P systems as the problem of uniquely generating a given graph by means of self-assembly P systems. In this respect, we show how to define a self-assembly P systems that uniquely generates a complete binary tree by using a “minimal” set of resources.

In this paper we present WebPS, an open-source web-enabled simulator for P systems, and a P accelerator for parallelization of the existing sequential simulators. The simulator is based on CLIPS, and it is already available as a web application. The P accelerator is used to parallelize the existing sequential simulators of the P systems. We exemplify this tool by using a simple CLIPS simulator. The speedup and the efficiency of the resulting parallel implementation are surprisingly close to the ideal ones. Combining these two ingredients, we get a complex and ready-to-use parallel simulator for P systems; no installation are required, no previous knowledge of operating systems, parallel programming or specific software.

We introduce a two-party communication complexity problem in which the probability of success by using a particular strategy allows the parties to detect with certainty whether or not some forbidden communication has taken place. We show that the probability of success is bounded by nature; any conceivable method which gives a probability of success outside these bounds is impossible. Moreover, any conceivable method to solve the problem which gives a probability success within these bounds is possible in nature. This example suggests that a suitably chosen set of communication complexity problems could be the basis of an information-theoretic axiomatization of quantum mechanics.

Membrane computing is a branch of molecular computing that aims to develop models and paradigms that are biologically motivated. It identifies an unconventional computing model, namely a P system, from natural phenomena of cell evolutions and chemical reactions. Because of the nature of maximal parallelism inherent in the model, P systems have a great potential for implementing massively concurrent systems in an efficient way that would allow us to solve currently intractable problems. In this paper, we look at various models of P systems and investigate their model-checking problems. We identify what is decidable (or undecidable) about model-checking these systems under extended logic formalisms of CTL. We also report on some experiments on whether existing conservative (symbolic) model-checking techniques can be practically applied to handle P systems with a reasonable size.

Earlier solutions to decision problems by means of P systems used many counter objects to control the synchronization of different stages in a computation (usually as many counters as the stage must last in the worst case). In this paper we propose a way to replace those counters with some spacial objects for each stage. Furthermore, following the ideas presented in [1], in order to have a common scheme to attack numerical problems, all instances of a problem with the same size are solved by the same P system (which depends on the size) given an input which describes the corresponding instance of the problem. We illustrate these ideas with a cellular solution to the Subset-Sum problem.