Search

This paper investigates operational semantics for various positive relevant logics without distribution after the work of Kit Fine in Models for Entailment. To invalidate the law of distribution of conjunction over disjunction, we use different types of states to model conjunction and disjunction, respectively. The implication → is interpreted by three operations ⊕ , ⊗ , ⊝, instead of one operation ‘·' as in Fine's work. [ABSTRACT FROM AUTHOR]

We introduce, and show the equivalences among, relativized versions of Brouwer's fan theorem for detachable bars (FAN), weak König lemma with a uniqueness hypothesis (WKL!), and the longest path lemma with a uniqueness hypothesis (LPL!) in the spirit of constructive reverse mathematics. We prove that a computable version of minimum principle: if f is a real valued computable uniformly continuous function with at most one minimum on {0,1}N, then there exists a computable α in {0,1}N such that $f(\alpha) = \inf f(\{0,1\}^\mathbf{N})$, is equivalent to some computably relativized version of FAN, WKL! and LPL!. [ABSTRACT FROM AUTHOR]

In this paper we introduce computable and time bounded Riemann surfaces, based on the classical abstract definition by charts. Building upon this definition we discuss computable versions of several classical results, such as the existence of complete continuations of holomorphic functions, universal coverings and the uniformization theorem (for some cases). Though we state most of our results for computable surfaces, many of them can also be transformed to a uniform version, i.e. based on representations of the class of Riemann surfaces (modulo conformal equivalence). [ABSTRACT FROM AUTHOR]

Given a tree T with costs on edges and a collection of terminal sets X = {S1, S2..., Sl}, the generalized Multicut problem asks to find a set of edges on T whose removal cuts every terminal set in X, such that the total cost of the edges is minimized. The standard version of the problem can be approximately solved by reducing it to the classical Multicut on trees problem. For the prize-collecting version of the problem, we give a primal-dual 3-approximation algorithm and a randomized 2.55-approximation algorithm (the latter can be derandomized). For the k-version of the problem, we show an interesting relation between the problem and the Densest k-Subgraph problem, implying that approximating the k-version of the problem within O(n1/6 − ε) for some small ε> 0 is hard. We also give a min { 2(l − k + 1), k }-approximation algorithm for the k-version of the problem via a nonuniform approach. [ABSTRACT FROM AUTHOR]

We survey and compare models of computation on real numbers exceeding the Church-Turing Hypothesis. [ABSTRACT FROM AUTHOR]

We consider the Sherali-Adams (SA) operator as a proof system for integer linear programming and prove linear lower bounds on the SA rank required to prove both the pigeon hole and least number principles. We also define the size of a SA proof and show that that while the pigeon hole principle requires linear rank, it only requires at most polynomial size. [ABSTRACT FROM AUTHOR]

We survey some work concerned with small universal Turing machines, cellular automata, and other simple models of computation. For example it has been an open question for some time as to whether the smallest known universal Turing machines of Minsky, Rogozhin, Baiocchi and Kudlek are efficient (polynomial time) simulators of Turing machines. These are some of the most intuitively simple computational devices and previously the best known simulations were exponentially slow. We discuss recent work that shows that these machines are indeed efficient simulators. As a related result we also find that Rule 110, a well-known elementary cellular automaton, is also efficiently universal. We also mention some new universal program-size results, including new small universal Turing machines and new semi-weakly universal Turing machines. We then discuss some ideas for future work arising out of these, and other, results. [ABSTRACT FROM AUTHOR]

Amorphous computing differs from the classical ideas about computations almost in every aspect. The architecture of amorphous computers is random, since they consist of a plethora of identical computational units spread randomly over a given area. Within a limited radius the units can communicate wirelessly with their neighbors via a single-channel radio. We consider a model whose assumptions on the underlying computing and communication abilities are among the weakest possible: all computational units are finite state probabilistic automata working asynchronously, there is no broadcasting collision detection mechanism and no network addresses. We show that under reasonable probabilistic assumptions non-uniform families of such amorphous computers can possess universal computing power with a high probability. To the best of our knowledge this is the first result showing the universality of such computing systems. [ABSTRACT FROM AUTHOR]

The intention of this talk is to look at various models of transfinite computation and give some calculations as to their comparative power. To clarify the kind of models that we are looking at, they will all be discrete acting: this will mean that they essentially perform simple discrete tasks in simple steps or stages. The reader should have in mind the paradigm of the standard Turing Machine which of course performs such simple actions as moving one cell left or right on the tape that it is reading, altering a symbol, changing a state etc etc. We are thus not considering any kind of machine or notional device that computes in an analogue fashion, nor any machine, such as neural network with nodes primed by infinitely precise real numbers, nor computations performed in chemistry beakers, across cell membranes, or in buckets of slime. [ABSTRACT FROM AUTHOR]

As one simple type of statistical inference problems we consider Most Likely Solution problem, a task of finding a most likely solution (MLS in short) for a given problem instance under some given probability model. Although many MLS problems are NP-hard, we propose, for these problems, to study their average-case complexity under their assumed probabality models. We show three examples of MLS problems, and explain that "message passing algorithms" (e.g., belief propagation) work reasonably well for these problems. Some of the technical results of this paper are from the author's recent joint work with his colleagues [WST, WY06, OW06] . [ABSTRACT FROM AUTHOR]

The input to a constraint satisfaction problem (CSP) consists of a set of variables, each with a domain, and constraints between these variables formulated by relations over the appropriate domains; the question is if there is an assignment of values to the variables that satisfies all constraints. Different algorithmic tasks for CSPs (checking satisfiability, counting the number of solutions, enumerating all solutions) can be used to model many problems in areas such as computational logic, artificial intelligence, circuit design, etc. We will survey results on the complexity of these computational tasks as a function of properties of the allowed constraint relations. Particular attention is paid to the special case of Boolean constraint relations. [ABSTRACT FROM AUTHOR]

We propose a tentative parallel between computational features and cellular operations in order to explore the possibility that the cell itself is intrinsically and not metaphorically a symbol-processing, computing entity. Central to this possible identification is the notion of virtuality, as understood in computational theory. [ABSTRACT FROM AUTHOR]

In this paper we prove that every nonzero $\Delta^0_2$e-degree is cuppable to 0e′ by a 1-generic $\Delta^0_2$e-degree (so low and nontotal) and that every nonzero ω-c.e. e-degree is cuppable to 0e′ by an incomplete 3-c.e. e-degree. [ABSTRACT FROM AUTHOR]

A jump inversion theorem for the degree spectra is presented. For a structure which degree spectrum is a subset of the jump spectrum of a structure , a structure is constructed as a Marker's extension of such that the jump spectrum of is exactly the degree spectrum of and the degree spectrum of is a subset of the degree spectrum of . [ABSTRACT FROM AUTHOR]

The conventional wisdom presented in most computability books and historical papers is that there were several researchers in the early 1930's working on various precise definitions and demonstrations of a function specified by a finite procedure and that they should all share approximately equal credit. This is incorrect. It was Turing alone who achieved the characterization, in the opinion of Gödel. We also explore Turing's oracle machine and its analogous properties in analysis. [ABSTRACT FROM AUTHOR]

P Systems with proteins on membranes were introduced recently by A.Paun and B. Popa, in an effort to bridge the gap between membrane computing and brane calculi. In this variant, one considers multisets of objects inside the membranes as well as proteins on the membranes. The action of the proteins on the objects is classified broadly into 5 categories. In this paper, we study the computational power of these actions and come up with upper and lower bounds in terms of computational power for some of them. [ABSTRACT FROM AUTHOR]

In the standard literature on inductive inference, a learner sees as input the course of values of the function to be learned. In the present work, it is investigated how reasonable this choice is and how sensitive the model is with respect to variations like the overgraph or undergraph of the function. Several implications and separations are shown and for the basic notions, a complete picture is obtained. Furthermore, relations to oracles, additional information and teams are explored. [ABSTRACT FROM AUTHOR]

We show that many so called discrete weak semilattices considered earlier in a series of author's publications have hereditary undecidable first-order theories. Since such structures appear naturally in some parts of computability theory, we obtain several new undecidability results. This applies e.g. to the structures of complete numberings, of m-degrees of index sets and of the Wadge degrees of partitions in the Baire space and ω-algebraic domains. [ABSTRACT FROM AUTHOR]

If a continuous function on a complete metric space has approximate roots and in a uniform manner at most one root, then it actually has a root. We validate this heuristic principle in Bishop-style constructive mathematics without countable choice, following Richman's way of defining the completion of a metric space as the set of all locations. MSC (2000): Primary 03F60; Secondary 03E25, 26E40, 54E50. [ABSTRACT FROM AUTHOR]

We present a hierarchy of families between the Σ2 and Δ3 levels of the arithmetic hierarchy. The structure of the top five levels of this hierarchy is in some sense similar to the structure of the Chomsky hierarchy, while the bottom levels are reminiscent of the bounded oracle query hierarchy. [ABSTRACT FROM AUTHOR]

How do ordinals gauge the strength and computational power of theories and what kind of information can be extracted from this correlation? This will be the guiding question of this talk. The connection between ordinal representation systems and theories is established in ordinal analysis, a central area of proof theory. The origins of proof theory can be traced back to the second problem on Hilbert's famous list of problems, which called for a proof of consistency of the arithmetical axioms of the reals. [ABSTRACT FROM AUTHOR]

The common formulation of the Church-Turing thesis runs as follows: Every computable partial function is computable by a Turing machine Where by partial function I mean a function from a subset of natural numbers to natural numbers. As most textbooks relate, the thesis makes a connection between an intuitive notion (computable function) and a formal one (Turing machine). The claim is that the definition of a Turing machine captures the pre-analytic intuition that underlies the concept computation. Formulated in this way the Church-Turing thesis cannot be proved in the same sense that a mathematical proposition is provable. However, it can be refuted by an example of a function which is not Turing computable, but is nevertheless calculable by some procedure that is intuitively acceptable. [ABSTRACT FROM AUTHOR]

In the information theoretic world, entropy is both the measure of randomness in a source and a lower bound for the compression achievable for that source by any encoding scheme. But when we must restrict ourselves to efficient schemes, entropy no longer captures these notions well. For example, there are distributions with very low entropy that nonetheless look random for polynomial-bound algorithms. Different notions of computational entropy have been proposed to take the role of entropy in such settings. Results in [GS91] and [Wee04]) suggest that when time bounds are introduced, the entropy of a distribution no longer coincides with the most effective compression for that source. This paper analyses three measures that try to capture the compressibility of a source, establishing relations and separations between them and analysing the two special cases of the uniform and the universal distribution mt over binary strings of a fixed size. It is shown that for the uniform distribution the three measures are equivalent and that for mt there is a clear separation between metric type entropy, and thus pseudo-entropy, and the maximum compressibility of a source. [ABSTRACT FROM AUTHOR]

Ballester has shown that the problem of deciding whether a Nash stable partition exists in a hedonic game with arbitrary preferences is NP-complete. In this paper we will prove that the problem remains NP-complete even when restricting to additively separable hedonic games. Bogomolnaia and Jackson have shown that a Nash stable partition exists in every additively separable hedonic game with symmetric preferences. We show that computing Nash stable partitions is hard in games with symmetric preferences. To be more specific we show that the problem of deciding whether a non trivial Nash stable partition exists in an additively separable hedonic game with non-negative and symmetric preferences is NP-complete. The corresponding problem concerning individual stability is also NP-complete since individually stable partitions are Nash stable and vice versa in such games. [ABSTRACT FROM AUTHOR]

I will give a brief account of how I came to introduce the term Hybrid System and to encourage it as a subject of study. I will also discuss what one should understand to pursue the subject fully, and also discuss the lines of development of my joint research with Wolf Kohn in this area. This is an area at the interface of mathematics, computer science, and control engineering, which has been pursued by many in all three areas since its inception. It can be thought of as the subject which deals with the interaction of discrete and continuous processes. This paper is intended to be legible to those without advanced analysis or differential geometry in their background. We concentrate on control, not on logics of hybrid systems, and aim at an audience unfamiliar with control. I make no apologies for not being technical. This is not a survey of the field. For a year 2000 survey see [1]. A survey made now would be very large. [ABSTRACT FROM AUTHOR]

We introduce the notion of a locally computable structure, a natural way of generalizing the notions of computable model theory to uncountable structures ${\mathcal{S}}$ by presenting the finitely generated substructures of $\S$ effectively. Our discussion emphasizes definitions and examples, but does prove two significant results. First, our notion of m-extensional local computability of ${\mathcal{S}}$ ensures that the Σn-theory of ${\mathcal{S}}$ will be Σn for all n ≤ m + 1. Second, our notion of perfect local computability is equivalent (for countable structures) to the classic definition of computable presentability. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper presents some new results about majority games. Isbell (1959) was the first to find a majority game without a minimum normalized integer representation; he needed 12 voters to construct such a game. Since then, it has been an open problem to find the minimum number of voters of a majority game without a minimum normalized integer representation. Our main new results are: 1. All majority games with less than 9 voters have a minimum integer representation. 2. For 9 voters, there are 14 majority games without a minimum integer representation, but all these games admit a minimum normalized integer representation. 3. For 10 voters, there exist majority games with neither a minimum integer representation nor a minimum normalized integer representation. [ABSTRACT FROM AUTHOR]

We expose a strict hierarchy within monotone monadic strict NP without inequalities (MMSNP), based on the number of second-order monadic quantifiers. We do this by studying a finer strict hierarchy within a class of forbidden patterns problems (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 monadic strict NP (MSNP). Our hierarchy results apply over a uniform signature involving a single binary relation, that is over digraphs. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider an extensional version, called qmTT, of the intensional 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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 NP 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. [ABSTRACT FROM AUTHOR]

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 ${\ensuremath{\omega^\omega}}$. Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than $\omega_1^{CK}$. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Effective domain theory is applied to fuzzy logic to give suitable notions of semi-decidable and decidable L-subset. The connection with the notions of fuzzy Turing machines and fuzzy grammar given in literature is also investigated. This shows the inadequateness of these definitions and the difficulties in formulating an analogue of Church Thesis for fuzzy logic. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 ωn + 1 can be found as the (maximal) order type of a set in a cumulative hierarchy of sets of rooted binary trees. [ABSTRACT FROM AUTHOR]

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 strict self-assembly 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 cannot strictly self-assemble in the Tile Assembly Model. We then define the fibered Sierpinski triangle, 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). [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We prove that for any k ≥ 3 each element of the homomorphic quasiorder of finite k-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 k-labeled trees, and of finite k-labeled trees with a fixed label of the root element. [ABSTRACT FROM AUTHOR]

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 AC0 and ACC0 are all computable by almost linear size circuits, extending the result of Chandra et al.[5]. [ABSTRACT FROM AUTHOR]

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 ΣK-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. [ABSTRACT FROM AUTHOR]

We show that the bounded arithmetic theory V0 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 ${\mbox{\rm{PV}}}$ under a cryptographic assumption. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In the paper the problem of existence of an algebraic structure with the degree spectra is studied for arbitrary degree . [ABSTRACT FROM AUTHOR]

We study Post's Problem for the ordinal register machines defined in [6], showing that its general solution is positive, but that any set of ordinals solving it must be unbounded in the writable ordinals. This mirrors the results in [3] for infinite-time Turing machines, and also provides insight into the different methods required for register machines and Turing machines in infinite time. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. Topics covered. Computability theoretic aspects of programs, computer virology. [ABSTRACT FROM AUTHOR]