27,544 results for ResearchSpace@Auckland

  • The Underlying Optimal Protocol of Rule 218 Cellular Automaton

    Goles, E; Littleland, Cedric; Rapaport, I (2007-11)

    Report
    The University of Auckland Library

    View record details
  • Forbidden Minors to Graphs with Small Feedback Sets

    Dinneen, Michael; Cattell, K; Fellows, M.R (1996-10)

    Report
    The University of Auckland Library

    Finite obstruction set characterizations for lower ideals in the minor order are guaran- teed to exist by the Graph Minor Theorem. In this paper we characterize several families of graphs with small feedback sets, namely k 1-Feedback Vertex Set, k 2-Feedback Edge Set and (k 1,k 2){Feedback Vertex/Edge Set, for small integer parameters k 1 and k 2. Our constructive methods can compute obstruction sets for any minor-closed family of graphs, provided the pathwidth (or treewidth) of the largest obstruction is known.

    View record details
  • Logical Equivalence Between Generalized Urn Models and Finite Automata

    Svozil, K (2002-02)

    Report
    The University of Auckland Library

    To every generalized urn model there exists a finite (Mealy) automaton with identical propositional calculus. The converse is true as well.

    View record details
  • Automatic linear orders and trees (Revised)

    Khoussainov, B; Rubin, S; Stephan, F (2003-11)

    Report
    The University of Auckland Library

    We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to Cantor-Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular we show that every infinite path in an automatic tree with countably many infinite paths is a regular language.

    View record details
  • P Systems with Active Membranes: Attacking NP Complete Problems

    Paun, G (1999-05)

    Report
    The University of Auckland Library

    P systems are parallel Molecular Computing models based on processing multisets of objects in cell-like membrane structures. Various variants were already shown to be computationally universal, equal in power to Turing machines. In this paper one proposes a class of P systems whose membranes are the main active components, in the sense that they directly mediate the evolution and the communication of objects. Moreover, the membranes can multiply themselves by division. We prove that this variant is not only computationally universal, but also able to solve NP complete problems in polynomial (actually, linear) time. We exemplify this assertion with the well-known SAT problem.

    View record details
  • Paradise Lost, or Paradise Regained?

    Bridges, D.S; Dediu, L.S (1997-09)

    Report
    The University of Auckland Library

    This paper outlines some of the history and philosophy of constructive mathematics, concentrating on the work of the late Errett Bishop and his followers.

    View record details
  • Computable Isomorphisms, Degree Spectra of Relations, and Scott Families

    Khoussainov, B; Shore, R.A (1997-04)

    Report
    The University of Auckland Library

    In studying effective structures we investigate the effective content of typical notions and constructions in many branches of mathematics including universal algebra and model theory. In particular, we are interested in the possibilities of effectivizing model-theoretic or algebraic constructions and the limits on these possibilities. For instance, we try to understand whether certain results of model theory (or universal algebra) can be carried out effectively. If not, we then try to discover sharp effective counterexamples. The systematic study of effectiveness in algebraic structures goes back to pioneering papers by Frölich and Shepherdson [11], Malcev [28][29], and Rabin [34] in the early 60s. Later in the early 70s, Nerode and his collaborators initiated combining algebraic constructions with priority arguments from computability theory thus beginning a new era in the development of the subject. Nowadays, there various approaches to effectiveness in structures. For example, Cenzer, Nerode, Remmel have been developing theory of p-time structures [6]. Khoussainov and Nerode have began the development of the theory of automatic structures [27]. In this paper we are interested in those structures in which the basic computations can be performed by Turing machines.

    View record details
  • Fitting Parameters for a Solvable Model of a Quantum Network (CDMTCS)

    Harmer, M. (2004-07)

    Report
    The University of Auckland Library

    A solvable model corresponding to a given quantum network is described in [22] without an explicit description of how to fit the parameters of the solvable model. Here we give a procedure to fit these parameters so that the solvable model reproduces the important features, viz. the scattering matrix for the physically relevant energies, of the quantum network, subject to the non-vanishing of a determinant.

    View record details
  • Reflections on Quantum Computing

    Calude, C.S; Dinneen, Michael; Svozil, K (2000-03)

    Report
    The University of Auckland Library

    In this rather speculative note three problems pertaining to the power and limits of quantum computing are posed and partially answered: a) when are quantum speedups possible?, b) is fixed-point computing a better model for quantum computing?, c) can quantum computing trespass the Turing barrier?

    View record details
  • LifeTime: A Unified Study of Life (A Preliminary Version)

    Meyerstein, F.W; Moller, A.P (2001-09)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Some Computability-Theoretical Aspects of Reals and Randomness

    Downey, R.G (2002-01)

    Report
    The University of Auckland Library

    We study computably enumerable reals (i.e. their left cut is computably enumerable) in terms of their spectra of representations and presentations. Then we study such objects in terms of algorithmic randomness, culminating in some recent work of the author with Hirschfeldt, Laforte, and Nies concerning methods of calibrating randomness.

    View record details
  • Disjunctive Sequences: An Overview

    Calude, C.S; Priese, L; Staiger, L (1997-10)

    Report
    The University of Auckland Library

    Following Jürgensen and Thierrin [21] we say that an infinite sequence is disjunctive if it contains any (finite) word, or, equivalently, if any word appears in the sequence infinitely many times. “Disjunctivity” is a natural qualitative property; it is weaker, than the property of “normality” (introduced by Borel [1]; see, for instance, Kuipers, Niederreiter [24]). The aim of this paper is to survey some basic results on disjunctive sequences and to explore their role in various areas of mathematics (e.g. in automata-theoretic studies of ω-languages or number theory). To achieve our goal we will use various instruments borrowed from topology, measure-theory, probability theory, number theory, automata and formal languages.

    View record details
  • Implementing Bead--Sort with P systems

    Arulanandham, J.J (2002-05)

    Report
    The University of Auckland Library

    In this paper, we implement Bead-Sort, a natural sorting algorithm we introduced in [1], with the new, biochemically inspired P systems. We make use of a special type of P system – a tissue P system that computes by means of communication (using symport/antiport rules) only.

    View record details
  • The Hausdorff Measure of Regular Omega-Languages is Computable

    Staiger, L (1998-08)

    Report
    The University of Auckland Library

    In several previous papers we have shown how to calculate Hausdor dimension and measure for certain classes of regular ω-languages (cf. [MS94], [St89], and [St93]). In this note we show that the results obtained in the papers [MS94] and [St93] can be used to give an effective procedure for the calculation of the Hausdor measure for arbitrary regular ω-languages.

    View record details
  • Is Complexity a Source of Incompleteness?

    Calude, C.S; Juergensen, H (2004-06)

    Report
    The University of Auckland Library

    In this paper we prove Chaitin’s “heuristic principle”, the theorems of a finitelyspecified theory cannot be significantly more complex than the theory itself, for an appropriate measure of complexity. We show that the measure is invariant under the change of the G¨odel numbering. For this measure, the theorems of a finitely-specified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like Zermelo-Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity, hence every sentence of the theory which is significantly more complex than the theory is unprovable. Previous results showing that incompleteness is not accidental, but ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence of length n is provable in the theory tends to zero when n tends to infinity, while the probability that a sentence of length n is true is strictly positive.

    View record details
  • Search and Enumeration Techniques for Incidence Structures

    Denny, P.C (1998-05)

    Report
    The University of Auckland Library

    This thesis investigates a number of probabilistic and exhaustive computational search techniques for the construction of a wide variety of combinatorial designs, and in particular, incidence structures. The emphasis is primarily from a computer science perspective, and focuses on the algorithmic development of the techniques, taking into account running time considerations and storage requirements. The search and enumeration techniques developed in this thesis have led to the discovery of a number of new results in the field of combinatorial design theory.

    View record details
  • Computable Isomorphism of Boolean Algebras with Operators

    Khoussainov, B; Kowalski, T (2002-03)

    Report
    The University of Auckland Library

    One of the central topics in computable algebra and model theory is concerned with the study of computable isomorphisms. Classically, we do not distinguish between isomorphic structures, however, from computability point of view, isomorphic structures can differ quite dramatically. A typical example is provided by the linear order of type ω. It has two computable copies such that in one the successor function is computable, but it is not computable in the other. These are clearly classically isomorphic, but they are not computably isomorphic.

    View record details
  • Randomness, Computability, and Algebraic Specifications

    Khoussainov, B (1996-08)

    Report
    The University of Auckland Library

    [no abstract available]

    View record details
  • Quasi-Apartness and Neighbourhood Spaces

    Ishihara, H; Mines, R; Schuster, P; Vita, L.S (2005-03)

    Report
    The University of Auckland Library

    We extend the concept of apartness spaces to the concept of quasi-apartness spaces. We show that there is an adjunction between the category of quasi-apartness spaces and the category of neighbourhood spaces, which indicates that quasi-apartness is a more natural concept than apartness. We also show that there is an adjoint equivalence between the category of apartness spaces and the category of Grayson’s separated spaces.

    View record details
  • A Constructive Proof of Gleason's Theorem

    Richman, F; Bridges, D.S (1997-05)

    Report
    The University of Auckland Library

    Gleason's theorem states that any totally additive measure on the closed subspaces, or projections, of a Hilbert space of dimension greater than two is given by a positive operator of trace class. In this paper we give a constructive proof of that theorem. A measure μ on the projections of a real or complex Hilbert space assigns to each projection P a nonnegative real number μ(P) such that if σ = ∑Pi, where the Pi are mutually orthogonal, then μ(σ) =∑μ(Pi). Such a measure is determined by its values on the one-dimensional projections. Let W be the measure of the identity projection, and Px the projection onto the 1-dimensional space spanned by the unit vector x. Then the measure μ is determined by the real-valued function f(x) = μ(Px) on the unit sphere, a function which has the property that [see pdf for formula] for each orthonormal basis E. Gleason calls such a function f a frame function of weight W. If T is a positive operator of trace class, then f(x) = ‹Tx,x› is a frame function. Gleason's theorem is that every frame function arises in this way. The original reference for Gleason's theorem is [4], which can also be found in Hooker [6]. Cooke, Keane and Moran [3] gave a proof that is elementary in the sense that it does not appeal to the theory of representations of the orthogonal group, which the original proof does. However, some of the reasoning in [3] seems hopelessly nonconstructive, so we follow the general outline of [4] until we come to the end of the 3-dimensional real case, at which point we modify some arguments in [3] rather than attempt a constructive development of the necessary representation theory. Any Hermitian form B on a finite-dimensional inner product space gives rise to a frame function f(x) = B(x; x) whose weight is equal to the trace of the matrix of B. The essence of Gleason's theorem is the following converse. -- from Introduction

    View record details