Catálogo de publicaciones - libros

In the paper the problem of existence of an algebraic structure with the degree spectra is studied for arbitrary degree .

We prove confluence of two cut-elimination procedures for the implicational fragment of a standard intuitionistic sequent calculus. One of the cut-elimination procedures uses global proof transformations while the other consists of local ones. Both of them include permutation of cuts to simulate -reduction in an isomorphic image of the -calculus. We establish the confluence properties through a conservativity result on the cut-elimination procedures.

We show that the bounded arithmetic theory V does not prove that the polynomial time hierarchy collapses to the linear time hierarchy (without parameters). This result follows from a lower bound for bounded depth circuits computing prefix parity, where the circuits are allowed some auxiliary input.

This is a continuation of earlier work by the authors which showed that this collapse is not provable in under a cryptographic assumption.

In this paper we prove the Uniformity Principle for –definability over the real numbers extended by open predicates. Using this principle we show that if we have a -formula, i.e. a formula with quantifier alternations where universal quantifiers are bounded by computable compact sets, then we can eliminate all universal quantifiers obtaining a -formula equivalent to the initial one. We also illustrate how the Uniformity Principle can be employed for reasoning about computability over continuous data in an elegant way.

We survey our current knowledge of circuit complexity of regular languages. We show that regular languages are of interest as languages providing understanding of different circuit classes. We also prove that regular languages that are in AC and ACC are all computable by almost linear size circuits, extending the result of Chandra et al.[5].

We prove that for any  ≥ 3 each element of the homomorphic quasiorder of finite -labeled forests is definable, provided that the minimal non-smallest elements are allowed as parameters. As corollaries, we show that the structure is atomic and characterize the automorphism group of the structure. Similar results hold true for two other relevant structures: the homomorphic quasiorder of finite -labeled trees, and of finite -labeled trees with a fixed label of the root element.

Realism about computation is the view that whether or not a particular physical system is performing a particular computation is at least sometimes a mindindependent feature of reality. The caveat ’at least sometimes’ is necessary here because a realist about computation need not believe that all instances of computation should be realistically construed. The computational theory of mind presupposes realism about computation. If whether or not the human nervous system implements particular computations is not a natural fact about the world that is independent of whether we represent it as doing so, then the computational theory of mind fails to naturalise the mind. Realism about computation is also presupposed by attempts to use computational principles such as Landauer’s Principle to dispel Maxwell’s Demon. Realism about computation has been challenged by Hilary Putnam and John Searle among others. Various arguments have been put forward purporting to show that any physical system of sufficient complexity trivially implements all computations. Ladyman et al. (2007) offer a precisification and general proof Landauer’s Principle. In order to do this they present an analysis of what it is for a physical process to implement a logical transformation. In this paper, their analysis is explained and its implications for realism about computation and the use of Landauer’s Principle in foundational debates is assessed.

Winfree (1998) showed that discrete Sierpinski triangles can self-assemble in the Tile Assembly Model. A striking molecular realization of this self-assembly, using DNA tiles a few nanometers long and verifying the results by atomic-force microscopy, was achieved by Rothemund, Papadakis, and Winfree (2004).

Precisely speaking, the above self-assemblies tile completely filled-in, two-dimensional regions of the plane, with labeled subsets of these tiles representing discrete Sierpinski triangles. This paper addresses the more challenging problem of the of discrete Sierpinski triangles, i.e., the task of tiling a discrete Sierpinski triangle and nothing else.

We first prove that the standard discrete Sierpinski triangle strictly self-assemble in the Tile Assembly Model. We then define the , a discrete Sierpinski triangle with the same fractal dimension as the standard one but with thin fibers that can carry data, and show that the fibered Sierpinski triangle strictly self-assembles in the Tile Assembly Model. In contrast with the simple XOR algorithm of the earlier, non-strict self-assemblies, our strict self-assembly algorithm makes extensive, recursive use of Winfree counters, coupled with measured delay and corner-turning operations. We verify our strict self-assembly using the local determinism method of Soloveichik and Winfree (2005).

Concerning the set of rooted binary trees, one shows that Higman’s Lemma and Dershowitz’s recursive path ordering can be used for the decision of its maximal order type according to the homeomorphic embedding relation as well as of the order type according to its canonical linearization, well-known in proof theory as the Feferman-Schütte notation system without terms for addition. This will be done by showing that the ordinal can be found as the (maximal) order type of a set in a cumulative hierarchy of sets of rooted binary trees.

A guiding question in the study of weak 2-randomness is whether weak 2-randomness is closer to 1-randomness, or closer to 2-randomness. Recent research indicates that the first alternative holds. We add further evidence in this direction by showing that, in contrast to the case for 2-randomness, a weakly 2-random set can fail to be generalized low.