Catálogo de publicaciones - libros

This chapter contains several original papers. These give the most essential sampling of the enormous body of material on the Riemann zeta function, the Riemann hypothesis, and related theory. They give a chronology of milestones in the development of the theory contained in the previous chapters. We begin with Chebyshev’s groundbreaking work on π(), continue through Riemann’s proposition of the Riemann hypothesis, and end with an ingenious algorithm for primality testing. These papers place the material in historical context and illustrate the motivations for research on and around the Riemann hypothesis. Most papers are preceded by a short biographical note on the author(s) and all are preceded by a short review of the material they present.

We consider the family of all the Cellular Automata (CA) sharing the same local rule but have different memory. This family contains also all the CA with memory  ≤ 0 (one-sided CA) which can act both on and on . We study several set theoretical and topological properties for these classes. In particular we investigate if the properties of a given CA are preserved when we consider the CA obtained by changing the memory of the original one (shifting operation). Furthermore we focus our attention to the one-sided CA acting on starting from the one-sided CA acting on and having the same local rule (lifting operation). As a particular consequence of these investigations, we prove that the long-standing conjecture [Surjectivity Density of the Periodic Orbits (DPO)] is equivalent to the conjecture [Topological Mixing DPO].

In this paper I describe the general principles of learning as data compression. I introduce two-part code optimization and analyze the theoretical background in terms of Kolmogorov complexity. The good news is that the optimal compression theoretically represents the optimal interpretation of the data, the bad news is that such an optimal compression cannot be computed and that an increase in compression not necessarily implies a better theory. I discuss the application of these insights to DFA induction.

There has been a great deal of progress in the fifteen years that have elapsed since Wigderson published his survey on the complexity of the graph connectivity problem [Wig92]. Most significantly, Reingold solved the longstanding question of the complexity of the - connectivity problem in undirected graphs, showing that this is complete for logspace (L) [Rei05].

This survey talk will focus on some of the remaining open questions dealing with graph reachability problems. Particular attention will be paid to these topics:

Realizability theory can produce interfaces for the data structure corresponding to a mathematical theory. Our tool, called RZ, serves as a bridge between constructive mathematics and programming by translating specifications in constructive logic into annotated interface code in Objective Caml. The system supports a rich input language allowing descriptions of complex mathematical structures. RZ does not extract code from proofs, but allows any implementation method, from handwritten code to code extracted from proofs by other tools.

The paper investigates different relationships between membrane systems and Petri nets by focusing on modelling variants of the producer/consumer paradigm. Two models of producer/consumer systems based on membrane systems are described, and it is shown how to translate these models into equivalent Petri nets with a corresponding semantics. It is then observed a direct correspondence between the Petri nets representation of the proposed models and standard solutions based on Petri nets already present in the literature.

In this paper, we prove the existence of a minimal pair of c.e. degrees a and b such that both of them are cuppable, and no incomplete c.e. degree can cup both of them to ′. As a consequence, [] and [] form a minimal pair in /, the quotient structure of the cappable degrees modulo noncuppable degrees. We also prove that the dual of Lempp’s conjecture is true.

This paper examines the constructive Hausdorff and packing dimensions of weak truth-table degrees. The main result is that every infinite sequence with constructive Hausdorff dimension dim() and constructive packing dimension dim() is weak truth-table equivalent to a sequence with , for arbitrary > 0. Furthermore, if dim() > 0, then dim() ≥ 1 − . The reduction thus serves as a that increases the algorithmic randomness of , as measured by constructive dimension.

A number of applications of this result shed new light on the constructive dimensions of wtt degrees (and, by extension, Turing degrees). A lower bound of dim() / dim() is shown to hold for the wtt degree of any sequence . A new proof is given of a previously-known zero-one law for the constructive packing dimension of wtt degrees. It is also shown that, for any sequence (that is, dim() = dim()) such that dim() > 0, the wtt degree of has constructive Hausdorff and packing dimension equal to 1.

Finally, it is shown that no single Turing reduction can be a constructive Hausdorff dimension extractor.

We study computer virology from an abstract point of view. Viruses and worms are self-replicating programs, whose constructions are essentially based on Kleene’s second recursion theorem. We show that we can classify viruses as solutions of fixed point equations which are obtained from different versions of Kleene’s second recursion theorem. This lead us to consider four classes of viruses which various polymorphic features. We propose to use virus distribution in order to deal with mutations.

Computability theoretic aspects of programs, computer virology.

We study the Borel complexity of topological operations on closed subsets of computable metric spaces. The investigated operations include set theoretic operations as union and intersection, but also typical topological operations such as the closure of the complement, the closure of the interior, the boundary and the derivative of a set. These operations are studied with respect to different computability structures on the hyperspace of closed subsets. These structures include positive or negative information on the represented closed subsets. Topologically, they correspond to the lower or upper Fell topology, respectively, and the induced computability concepts generalize the classical notions of r.e. or co-r.e. subsets, respectively. The operations are classified with respect to effective measurability in the Borel hierarchy and it turns out that most operations can be located in the first three levels of the hierarchy, or they are not even Borel measurable at all. In some cases the effective Borel measurability depends on further properties of the underlying metric spaces, such as effective local compactness and effective local connectedness.