Catálogo de publicaciones - libros

Recently, the idea of spiking neurons and thus of computing by spiking was incorporated into membrane computing, and so-called spiking neural P systems (abbreviated SN P systems) were introduced. Very shortly, in these systems neurons linked by synapses communicate by exchanging identical signals (spikes), with the information encoded in the distance between consecutive spikes. Several ways of using such devices for computing were considered in a series of papers, with universality results obtained in the case of computing numbers, both in the generating and the accepting mode; generating, accepting, or processing strings or infinite sequences was also proved to be of interest.

In the present paper, after a short survey of central notions and results related to spiking neural P systems (including the case when SN P systems are used as string generators), we contribute to this area with two (types of) results: (i) we produce small universal spiking neural P systems (84 neurons are sufficient in the basic definition, but this number is decreased to 49 neurons if a slight generalization of spiking rules is adopted), and (ii) we investigate the possibility of generating a language by following the trace of a designated spike in its way through the neurons.

Minimal parallelism was recently introduced [3] as a way the rules of a P system are used: from each set of applicable rules associated to the same membrane, at least one must be applied. In this paper, we consider the minimal parallelism for P systems with active membranes , using additional features, such as separation operations, changing membrane labels, catalytic or cooperative rules, etc. With several combinations of such features we obtain computational completeness. In cases where membrane division (of elementary or non-elementary membranes) is allowed, we show how SAT can be solved in polynomial time.

A P system is a natural computing model inspired by information processes in cells and a control role of cellular membranes. We show that uniform families of P systems with active membranes are able to solve, in polynomial time, exactly the class of decisional problems . Similar results were achieved also with other models of bio-inspired computers, such as DNA computing. Together they suggest that naturally characterizes the computational potential of biological information processing.

In this paper, we present two new results regarding ANSPs. The first one states that every recursively enumerable language can be accepted by an ANSP of size 7 out of which 6 do not depend on the given language. Then we propose a method for constructing, given an -language, an ANSP of size 7 accepting that language in polynomial time. Unlike the previous case, all nodes of this ANSP depend on the given language. Since each ANSP may be viewed as a problem solver as shown in [6], the later result may be interpreted as a method for solving every -problem in polynomial time by an ANSP of size 7.

In this article we propose a formalization of protocols simulating the separation of molecules by gel electrophoresis. In our model, we introduce a new concept, namely, filtering by length – a direct formalization of the gel electrophoresis action. We also define a distributed computational model based on this action and on the splicing operation, called length-separating splicing test tube systems. We prove that these constructs, even with restricted size parameters, can simulate the Turing machines. We also discuss different natural restrictions and generalizations of the model which may be used to find efficient ways to realize DNA transformations in the laboratory.

The micronuclear genes in stichotrichous ciliates are interrupted by multiple non-coding DNA segments. The coding segments are in scrambled disorder and can also be inverted. Identical short sequences (pointers) at the ends of the coding segments undergo homologous recombination to excise the non-coding segments and splice the coding ones. We consider the intramolecular model of Prescott, Ehrenfeucht, and Rozenberg for gene assembly in stichotrichous ciliates from the algorithmic point of view. We give a quadratic time algorithm for finding a successful sequence of operations to assemble a gene. We also prove an Ω(log) lower bound on the amount of work needed to assemble genes, even when any pair of identical pointers have the same orientation. For the problem of finding the minimum number of operations needed to assemble a given gene, we give a heuristic quadratic algorithm which works well in practice. The complexity of this problem remains open.

Given a set of flexible branched junction DNA molecules (building blocks) with sticky ends we consider the question of determining the proper stoichiometry such that all sticky ends could end up connected. The idea is to determine the proper proportion (spectrum) of each type of molecules present, which in general is not uniform. We classify the pot in three classes: weakly satisfiable, satisfiable and strongly satisfiable according to possible components that assemble in complete complexes. This classification is characterized through the spectrum of the pot, which can be computed in PTIME using the standard Gauss-Jordan elimination method.

We study the complexity of the Accretive Graph Assembly Problem (AGAP). An instance of AGAP consists of an edge-weighted graph , a seed vertex in , and a temperature . The goal is to determine if there is a sequence of vertex additions which constructs starting from the seed. The edge weights model the forces of attraction and repulsion, and determine which vertices can be added to a partially assembled graph at the given temperature.

Our first result is that AGAP is NP-complete even on degree 3 planar graphs when edges have only two different types of weights. This resolves the complexity of AGAP in the sense that the problem is polytime solvable when either the degree is bounded by 2 or the number of distinct edge weights is one, and is NP-complete otherwise. Our second result is a dichotomy theorem that completely characterizes the complexity of AGAP on degree 3 bounded graphs with two distinct weights: , . We give a simple system of linear constraints on , , and that determines whether the problem is NP-complete or is polytime solvable. In the process of establishing this dichotomy, we give the first polytime algorithm to solve a non-trivial class of AGAP Finally, we consider the optimization version of AGAP where the goal is to realize a largest-possible subgraph of the given input graph. We show that even on constructible graphs of degree at most 3, it is NP-hard to realize a (1/)-fraction of the input graph for any > 0; here denotes the number of vertices in .

Viruses compress their genome to reduce space. One of the main techniques is overlapping genes. We model this process by the shortest common superstring problem, that is, we look for the shortest genome which still contains all genes. We give an algorithm for computing optimal solutions which is slow in the number of strings but fast (linear) in their total length. This algorithm is used for a number of viruses with relatively few genes. When the number of genes is larger, we compute approximate solutions using the greedy algorithm which gives an upper bound for the optimal solution. We give also a lower bound for the shortest common superstring problem. The results obtained are then compared with what happens in nature. Remarkably, the compression obtained by viruses is quite high and also very close to the one achieved by modern computers.

One of the main research topics in DNA computing is associated with the design of information encoding single or double stranded DNA strands that are “suitable” for computation. Double stranded or partially double stranded DNA occurs as a result of binding between complementary DNA single strands ( is complementary to and is complementary to ). This paper continues the study of the algebraic properties of DNA word sets that ensure that certain undesirable bonds do not occur. We formalize and investigate such properties of sets of sequences, e.g., where no complement of a sequence is a prefix or suffix of another sequence or no complement of a concatenation of sequences is a subword of the concatenation of + 1 sequences. The sets of code words that satisfy the above properties are called – prefix, -suffix and -intercode respectively, where is the formalization of the Watson-Crick complementarity. Lastly we develop certain methods of constructing such sets of DNA words with good properties and compute their informational entropy.