Catálogo de publicaciones - libros

A classic result known as the speed-up theorem in machine-independent complexity theory shows that there exist some computable functions that do not have best programs for them [2][3]. In this paper we lift this result into type-2 computation under the notion of our type-2 complexity theory depicted in [15][13][14]. While the speed-up phenomenon is essentially inherited from type-1 computation, we cannot directly apply the original proof to our type-2 speed-up theorem because the oracle queries can interfere the speed of the programs and hence the cancellation strategy used in the original proof is no longer correct at type-2. We also argue that a type-2 analog of the operator speed-up theorem [16] does not hold, which suggests that this curious phenomenon disappears in higher-typed computation beyond type-2.

The Ordinal Register Machine (ORM) is one of several different machine models for infinitary computability. We classify, by complexity, the sets that can be decided quickly by ORMs. In particular, we show that the arithmetical sets are exactly those sets that can be decided by ORMs in times uniformly less than . Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than .

In this paper, we show that accepting networks of splicing processors (ANSPs) of size 3 are computationally complete. Moreover, we prove that they can decide all languages in in polynomial time. The previous lower bound for both issues was 7. Since, by its definition, ANSPs need at least 2 nodes for any non-trivial computation, we leave only one open case. We also prove the following normal form: For any ANSP there exists an equivalent ANSP without output filters.

This review addresses structural differences between that type of computation on which computability theory and computational complexity theory have focused so far, and those computations that are usually carried out in biological organisms (either in the brain, or in the form of gene regulation within a single cell). These differences concern the role of time, the way in which the input is presented, the way in which an algorithm is implemented, and in the end also the definition of what a computation is. This article describes liquid computing as a new framework for analyzing those types of computations that are usually carried out in biological organisms.

We consider an version, called qmTT, of the Minimal Type Theory mTT, introduced in a previous paper with G. Sambin, enriched with proof-irrelevance of propositions and effective quotient sets. Then, by using the construction of total setoid à la Bishop we build a model of qmTT over mTT.

The design of an extensional type theory with quotients and its interpretation in mTT is a key technical step in order to build a two level system to serve as a minimal foundation for constructive mathematics as advocated in the mentioned paper about mTT.

We define the hairpin reduction as the inverse operation of a formal operation on words and languages suggested by DNA biochemistry, namely the hairpin completion, introduced in [3]. We settle the closure properties of some classes in the Chomsky hierarchy as well as some complexity classes under the non-iterated version of the hairpin reduction, in comparison with the hairpin completion. Then an algorithm that decides whether or not a regular language coincides with its primitive hairpin root is presented. Finally, we discuss a cubic time algorithm for computing the common ancestors of two given words. This algorithm may be used also for computing the closest or farthest primitive hairpin root of a given word.

We expose a strict hierarchy within NP (MMSNP), based on the number of second-order monadic quantifiers. We do this by studying a finer strict hierarchy within a class of (FPP), based on the number of permitted colours. Through an adaptation of a preservation theorem of Feder and Vardi, we are able to prove that this strict hierarchy also exists in NP (MSNP). Our hierarchy results apply over a uniform signature involving a single binary relation, that is over digraphs.

P-systems, or membrane systems [1], were introduced by George Păun as a class of unconventional computing devices of distributed, parallel and nondeterministic type, inspired by the compartmental structure and the functioning of living cells. The basic model consists of a membrane structure, described by a finite string of well matching parentheses, and graphically represented as regions on the plane, hierarchically embedded within an external region. Each membrane contains a multiset of (representing chemical substances) that evolve according to given (representing reactions).

In this paper we survey previous work by the authors defining a complexity measure for certain continuous time systems. Starting point are energy functions of a particular structure. Global minimizers of such energies correspond to solutions of a given problem, for example an equilibrium point of an ordinary differential equation. The structure of such energies is used to define complexity classes for continuous problems and to obtain completeness results for those classes. We discuss as well algorithmic aspects of minimizing energy functions.

We study possible spectrums of torsion free Abelian groups. We code families of finite sets into group and set up the correspondence between their algorithmic complexities.