Catálogo de publicaciones - libros

The emergence of terms like , evolutionary computing, etc., shows the never ending interest of the computer scientists for the use of “natural phenomena” as “problem solving devices” or more generally, as a fruitful source of inspiration to develop new programming paradigms. It is the latter topic which interests us here. The idea of numerical experiment can be reversed and, instead of using computers to simulate a fragment of the real world, the idea is to use (a digital simulation of) the real world to compute. In this perspective, the processes that take place in the real world are the objects of a new calculus:

description of the world’s laws = program

state of the world = data of the program

parameters of the description = inputs of the program

simulation = the computation

This is just a glimpse to the fruitful and continuous preoccupation of computer science to try to get inspired by biology, at various levels. Besides briefly discussing the main areas of natural computing (genetic algorithms–evolutionary computing, neural computing, DNA computing, and membrane computing), we mention some of the hopes and the difficulties/limits of this enterprise.

Evolving solutions rather than computing them certainly represents an unconventional programming approach. The general methodology of evolutionary computation has already been known in computer science since more than 40 years, but their utilization to program other algorithms is a more recent invention. In this paper, we outline the approach by giving an example where evolutionary algorithms serve to program cellular automata by designing rules for their iteration. Three different goals of the cellular automata designed by the evolutionary algorithm are outlined, and the evolutionary algorithm indeed discovers rules for the CA which solve these problems efficiently.

Self-assembly is the spontaneous self-ordering of substructures into superstructures, driven by the selective affinity of the substructures. Complementarity of DNA bases renders DNA an ideal material for programmable self-assembly of nanostructures. DNA self-assembly is the most advanced and versatile system that has been experimentally demonstrated for programmable construction of patterned systems on the molecular scale. The methodology of DNA self-assembly begins with the synthesis of single strand DNA molecules that self-assemble into macromolecular building blocks called DNA tiles. These tiles have single strand “sticky ends” that complement the sticky ends of other DNA tiles, facilitating further assembly into larger structures known as DNA tiling lattices. In principle, DNA tiling assemblies can form any computable two or three-dimensional pattern, however complex, with the appropriate choice of the tiles’ component DNA. Two-dimensional DNA tiling lattices composed of hundreds of thousands of tiles have been demonstrated experimentally. These assemblies can be used as programmable scaffolding to position molecular electronics and robotics components with precision and specificity, facilitating fabrication of complex nanoscale devices. We overview the evolution of DNA self-assembly techniques from pure theory, through simulation and design, and then to experimental practice. In particular, we begin with an overview of theoretical models and algorithms for DNA lattice self-assembly. Then we describe our software for the simulation and design of DNA tiling assemblies and DNA nano-mechanical devices. As an example, we discuss models, algorithms, and computer simulations for the key problem of error control in DNA lattice self-assembly. We then briefly discuss our laboratory demonstrations of DNA lattices and motors, including those using the designs aided by our software. These experimental demonstrations of DNA self-assemblies include the assembly of patterned objects at the molecular scale, the execution of molecular computations, and the autonomous DNA walking and computing devices.

Membrane Computing (MC) is part of the powerful trend in computer science known under the name of Natural Computing. Its goal is to abstract computing models from the structure and the functioning of the living cell. The present paper is a short and informal introduction to MC, presenting the basic ideas, the central (types of) results, and the main directions of research.

Adaptable executions inspired by the cell behaviour can be described by a cellular meta-programming paradigm. The cell adaptability and meta-programming are related to the notions of behavioural reflection, which allows a program to modify, even at run-time, its own code as well as the semantics of its own programming language. We present the cellular meta-programming considering the membrane systems and a specification language based on rewriting and allowing meta-level strategies and use of reflection.

The dynamic nature of biological systems’ structure, and the continuous evolution of their components require new modelling approaches. In this paper it will be investigated how these systems composed of many dynamic components can be formally modelled as well as how their configurations can be altered, thus affecting the communication between parts. We use two different formal methods, communicating X-machines and population P systems, both with dynamic structures. It will be shown that new modelling approaches are required in order to capture the complex and dynamic nature of these systems.

Let R = {r, ..., r} be the set of labeled rules in a system. We look at the computing power of the system under three semantics of parallelism. For a positive integer n ≤ k, define:

At each step, nondeterministically select a maximal subset of at most rules in to apply.

≤ At each step, nondeterministically select any subset of at most rules in to apply.

At each step, nondeterministically select any subset of exactly rules in to apply.

Note that in all three cases, at most one instance of any rule can be included in the selected subset. Moreover, if any rule in the subset selected is not applicable, then the whole subset is not applicable. When n = 1, the three semantics reduce to the mode.

For two models of systems that have been studied in the literature, catalytic systems and communicating systems, we show that n mode is strictly more powerful than any of the following three modes: , ≤ , or . For example, it follows from a previous result that a 3 communicating system is universal. However, under the three limited modes of parallelism, the system is equivalent to a vector addition system, which is known to only define a recursive set. This shows that gmaximal parallelismh (in the sense of) is key for the model to be universal.

We also summarize our recent results concerning membrane hierarchy, determinism versus nondeterminism, and computational complexity of systems. Finally, we propose some problems for future research.

Some of the results presented here were obtained in collaboration with Zhe Dang and Hsu-Chun Yen.

The quest for novel and unconventional computing machines is mainly motivated by the man-machine dichotomy and by the belief that dealing with new physical computing substrates, new environments, and new applications will require new paradigms to organize, train, program, and to interact with them. The goal of this contribution is to delineate a possible way to address the general scientific challenge of seeking for further progress and new metaphors in computer science by means of unconventional approaches. Here we outline an amalgamation of (1) a particle-based, randomly interconnected, and reconfigurable substrate, (2) membrane systems, and (3) artificial chemistries in combination with (4) an unconventional adaptation paradigm.

The increasing scale complexity, heterogeneity and dynamism of networks, systems and applications have made our computational and information infrastructure brittle, unmanageable and insecure. This has necessitated the investigation of an alternate paradigm for system and application design, which is based on strategies used by biological systems to deal with similar challenges – a vision that has been referred to as autonomic computing. The overarching goal of autonomic computing is to realize computer and software systems and applications that can manage themselves in accordance with high-level guidance from humans. Meeting the grand challenges of autonomic computing requires scientific and technological advances in a wide variety of fields, as well as new software and system architectures that support the effective integration of the constituent technologies. This paper presents an introduction to autonomic computing, its challenges, and opportunities.