27,544 results for ResearchSpace@Auckland

The Underlying Optimal Protocol of Rule 218 Cellular Automaton
Goles, E; Littleland, Cedric; Rapaport, I (200711)
Report
View record details
The University of Auckland Library 
Forbidden Minors to Graphs with Small Feedback Sets
Dinneen, Michael; Cattell, K; Fellows, M.R (199610)
Report
The University of Auckland LibraryFinite 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 1Feedback Vertex Set, k 2Feedback 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 minorclosed 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 (200202)
Report
The University of Auckland LibraryTo 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 (200311)
Report
The University of Auckland LibraryWe 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 CantorBendixson 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 (199905)
Report
The University of Auckland LibraryP systems are parallel Molecular Computing models based on processing multisets of objects in celllike 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 wellknown SAT problem.
View record details 
Paradise Lost, or Paradise Regained?
Bridges, D.S; Dediu, L.S (199709)
Report
The University of Auckland LibraryThis 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 (199704)
Report
The University of Auckland LibraryIn 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 modeltheoretic 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 ptime 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. (200407)
Report
The University of Auckland LibraryA 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 nonvanishing of a determinant.
View record details 
Reflections on Quantum Computing
Calude, C.S; Dinneen, Michael; Svozil, K (200003)
Report
The University of Auckland LibraryIn 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 fixedpoint 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 (200109)
Report
The University of Auckland Library[no abstract available]
View record details 
Some ComputabilityTheoretical Aspects of Reals and Randomness
Downey, R.G (200201)
Report
The University of Auckland LibraryWe 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 (199710)
Report
The University of Auckland LibraryFollowing 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 automatatheoretic studies of ωlanguages or number theory). To achieve our goal we will use various instruments borrowed from topology, measuretheory, probability theory, number theory, automata and formal languages.
View record details 
Implementing BeadSort with P systems
Arulanandham, J.J (200205)
Report
The University of Auckland LibraryIn this paper, we implement BeadSort, 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 OmegaLanguages is Computable
Staiger, L (199808)
Report
The University of Auckland LibraryIn 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 (200406)
Report
The University of Auckland LibraryIn 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 finitelyspecified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like ZermeloFraenkel 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 (199805)
Report
The University of Auckland LibraryThis 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 (200203)
Report
The University of Auckland LibraryOne 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 (199608)
Report
The University of Auckland Library[no abstract available]
View record details 
QuasiApartness and Neighbourhood Spaces
Ishihara, H; Mines, R; Schuster, P; Vita, L.S (200503)
Report
The University of Auckland LibraryWe extend the concept of apartness spaces to the concept of quasiapartness spaces. We show that there is an adjunction between the category of quasiapartness spaces and the category of neighbourhood spaces, which indicates that quasiapartness 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 (199705)
Report
The University of Auckland LibraryGleason'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 onedimensional projections. Let W be the measure of the identity projection, and Px the projection onto the 1dimensional space spanned by the unit vector x. Then the measure μ is determined by the realvalued 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 3dimensional 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 finitedimensional 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