101 results for Report, 1997

Adjoints, Absolute Values and Polar Decompostions
Bridges, D.S; Richman, F; Schuster, P (199711)
Report
The University of Auckland LibraryVarious questions about adjoints, absolute values and polar decompositions of operators are addressed from a constructive point of view. The focus is on bilinear forms. Conditions are given for the existence of an adjoint, and a general notion of a polar decomposition is developed. The Riesz representation theorem is proved without countable choice.
View record details 
Small Trivalent Graphs of Large Girth
Conder, M (199706)
Report
The University of Auckland LibraryDefinitions are given for seven trivalent Cayley graphs, of girths 17; 18; 20; 21; 22; 23 and 24. At the time of writing (June 1997) each of these is the smallest known trivalent graph of the corresponding girth.
View record details 
Computational Complementarity and Sofic Shifts
Calude, C.S; Lipponen, M (199708)
Report
The University of Auckland LibraryFinite automata (with outputs but no initial states) have been extensively used as models of computational complementarity, a property which mimics the physical complementarity. All this work was focussed on “frames", i.e., on fixed, static, local descriptions of the system behaviour. In this paper we are mainly interested in the asymptotical description of complementarity. To this aim we will study the asymptotical behaviour of two complementarity principles by associating to every incomplete deterministic automaton (with outputs, but no initial state) certain sofic shifts: automata having the same behaviour correspond to a unique sofic shift. In this way, a class of sofic shifts reflecting complementarity will be introduced and studied. We will prove that there is a strong relation between “local complementarity", as it is perceived at the level of “frames", and “asymptotical complementarity" as it is described by the sofic shift.
View record details 
Nonassociative Computable Rings and Their Isomorphisms. (1997)
Khoussainov, B.; Slinko, A. (199708)
Report
The University of Auckland LibraryWe investigate computable isomorphism types of (nonassociative) rings. We prove that for any n Є ω U {ω} there exists a ring with exactly n computable isomorphism types. We also investigate the relationship between the number of computable isomorphism types of a ring and the number of computable isomorphism types of its expansion by a finite number of constants.
View record details 
Practical Enumeration Methods for Graphs of Bounded Pathwidth and Treewidth
Dinneen, Michael (199709)
Report
The University of Auckland LibraryUsing an algebraic representation for graphs of bounded pathwidth or treewidth we provide simple methods for generating these families in increasing order of the number of vertices and edges. We also study canonic representions of fixed and free boundaried graphs of bounded width.
View record details 
Chaitin Omega Numbers and Strong Reducibilities
Calude, C.S; Nies, A (199710)
Report
The University of Auckland LibraryWe prove that any Chaitin Ω number (i.e., the halting probability of a universal selfdelimiting Turing machine) is wttcomplete, but not ttcomplete. In this way we obtain a whole class of natural examples of wttcomplete but not ttcomplete r.e. sets. The proof is direct and elementary.
View record details 
Invariance Properties of Random Sequences
Hertling, P; Wang, Y (199710)
Report
The University of Auckland LibraryWe present invariance characterizations of different types of random sequences. We correct Schnorr's original, incorrect characterization of MartinLöf random sequences, compare it with Schnorr's corresponding characterization of his own randomness concept, and give a similar, new chararacterization of Kurtz random sequences. That is, we show that an infinite sequence ξ is Kurtz random if and only if for every partial, computable, measureinvariant function φ: ∑ ω→∑ ω the sequence φ (ξ) is not recursive.
View record details 
Feedback for Relations
Cazanescu, V.E (199711)
Report
The University of Auckland LibraryIn our previous papers [3,2] we have proved that there are nine types of finite relations which are closed under a natural definition of feedback. In this note we prove that this natural definition is the unique feedback which satisfies the axioms of a biflow over there usual composition and sum.
View record details 
Embedding Quantum Universes into Classical Ones
Calude, C.S; Hertling, P.H; Svozil, K (199705)
Report
The University of Auckland LibraryDo the partial order and lattice operations of a quantum logic correspond to the logical implication and connectives of classical logic? Rephrased, how far might a classical understanding of quantum mechanics be, in principle, possible? A celebrated result by Kochen and Specker answers the above question in the negative. However, this answer is just one among different possible ones, not all negative. It is our aim to discuss the above question in terms of mappings of quantum worlds into classical ones, more specifically, in terms of embeddings of quantum logics into classical logics; depending upon the type of restrictions imposed on embeddings the question may get negative or positive answers.
View record details 
Constructive Mathematics, in Theory and Programming Practice
Bridges, D.S; Reeves, S (199711)
Report
The University of Auckland LibraryThe first part of the paper introduces the varieties of modern constructive mathematics, concentrating on Bishop's constructive mathematics (BISH). It gives a sketch of both Myhill's axiomatic system for BISH and a constructive axiomatic development of the real line R. The second part of the paper focusses on the relation between constructive mathematics and programming, with emphasis on MartinLöf's theory of types as a formal system for BISH.
View record details 
Linear Independence and Choice
Bridges, D.S; Richman, F; Schuster, P (199705)
Report
The University of Auckland LibraryThe notions of linear and metric independence are investigated in relation to the property: if U is a set of m + 1 independent vectors, and X is a set of m independent vectors, then adjoining some vector in U to X results in a set of m + 1 independent vectors. A weak countable choice axiom is introduced, in the presence of which linear and metric independence are equivalent. Proofs are carried out in the context of intuitionistic logic.
View record details 
Surjective Functions on Computably Growing Cantor Sets
Hertling, P (199710)
Report
The University of Auckland LibraryEvery infinite binary sequence is Turing reducible to a random one. This is a corollary of a result of Peter Gacs stating that for every cor.e. closed set with positive measure of infinite sequences there exists a computable mapping which maps a subset of the set onto the whole space of infinite sequences. Cristian Calude asked whether in this result one can replace the positive measure condition by a weaker condition not involving the measure. We show that this is indeed possible: it is sufficient to demand that the cor.e. closed set contains a computably growing Cantor set. Furthermore, in the case of a set with positive measure we construct a surjective computable map which is more effective than the map constructed by Gacs.
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 
Recursively Enumerable Reals and Chaitin Omega Numbers
Calude, C.S; Hertling, P.H; Khoussainov, B; Wang, Y (199710)
Report
The University of Auckland LibraryA real α is called recursively enumerable if it can be approximated by an increasing, recursive sequence of rationals. The halting probability of a universal self delimiting Turing machine (Chaitin's Ω number, [10]) is a random r.e. real. Solovay's [25] Ωlike reals are also random r.e. reals. Solovay showed that any Chaitin Ω number is Ωlike. In this paper we show that the converse implication is true as well: any Ωlike real in the unit interval is the halting probability of a universal selfdelimiting Turing machine. Following Solovay [25] and Chaitin [11] we say that an r.e. real α dominates an r.e. real β if from a good approximation of α from below one can compute a good approximation of β from below. We shall study this relation and characterize it in terms of relations between r.e. sets. Ωlike numbers are the maximal r.e. real numbers with respect to this order, that is, from a good approximation to an Ωlike real one can compute a good approximation for every r.e. real. This property shows the strength of Ω for approximation purposes. However, the situation is radically different if one wishes to compute digits of the binary expansion of an r.e. real: one cannot compute with a total recursive function the first n digits of the r.e. real 0:¬xK (the characteristic sequence of the halting problem) from the first g(n) digits of Ω, for any total recursive function g.
View record details 
Digital Geometry: Introduction and Bibliography
Rosenfeld, Azriel (1997)
Report
The University of Auckland LibraryYou are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (fortyfive) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/1997/CITRTR1.pdf under terms that include this permission. All other rights are reserved by the author(s). Digital geometry deals with geometrical properties of "digital objects", which are usually taken to be sets of lattice points in the discrete space Zⁿ. Such objects are often the result of applying a "digitization" process to objects in the Euclidean space Rⁿ. A central theme in digital geometry is how to characterize digital objects that could be the digitizations of "real" objects that have given geometric properties. The literature on digital geometry dates back to the late 1960's. The report includes a bibliography of more then 900 papers on the subject, organized by topic. It outlines the main lines of development of the field, and indicates areas in which interesting problems remain open.
View record details 
A Modular 10DOF Vision System for HighResolution Active Stereo
Schlüns, Karsten; Fellenz, Winfried; Koschan, Andreas; Teschner, Matthias (1997)
Report
The University of Auckland LibraryWe present a lowcost active vision system with ten degrees of freedom which has been built from offtheshelf parts. To obtain high resolution depth information of fixated objects in the scene a general purpose calibration procedure is proposed which estimates intrinsic and extrinsic camera parameters including the vergence axes of both cameras. To produce enhanced dense depth maps a hierarchical block matching procedure is presented which employs color information. To simplify the development of controlling strategies for the head a modular hierarchy is proposed that distributes various tasks among different levels employing basic capabilities of the components of the head.
View record details 
Evaluation of MPEG Motion Compensation Algorithms
Stegner, Axel; Klette, Reinhard (1997)
Report
The University of Auckland LibraryYou are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (fortyfive) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). This paper describes ongoing research about the development of an evaluation scheme which allows an objective comparison of different motion detection algorithms used while compressing image sequences: "real world" sequences as well as generated sequences containing special textures or objects. Its focus is on block motion detection algorithms used by MPEG video encoding and the goal is to develop an objective motion compensation quality.
View record details 
Shading Based 3D Shape Recovery in the Presence of Shadows
Schlüns, Karsten (1997)
Report
The University of Auckland LibraryYou are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (fortyfive) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). Shadows usually cause various problems in threedimensional shape recovery and measurement methods. In particular shading based approaches such as shapefromshading or the photometric stereo method produce no or wrong results if the shadows are not treated appropriately. We show how information extracted from shadows can be employed to reduce the problems caused by them. This is done for multiple lightsource photometric stereo. Unlike other published work, we formulate sufficient conditions to recover locally unique surface normals from two image irradiances (intensities) and a zeroirradiance caused by a shadow. We also distinguish between selfshadows and castshadows. Moreover we show how much information is obtainable by using the shadow analysis.
View record details 
The Irradiance Error and its Effect in Photometric Stereo
Schlüns, Karsten (1997)
Report
The University of Auckland LibraryYou are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (fortyfive) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). This paper discusses some essential aspects on evaluating the threesource photometric stereo method (PSM). PSM is a shading based 3D shape recovery approach that calculates a dense set of surface orientations from three input images taken by changing the illumination direction without moving the optical sensor. A subsequent step can be used to convert the surface gradients into a dense height map by means of an integration method. In a previous paper [2] we carried out evaluations of integration approaches. Here we show how the resolution of surface orientations depends on perturbations in the image irradiances (intensities). Previous methods considered only single light source configurations or particular image irradiance triples, hence no general predictions could be made. We give a simple geometrical interpretation to estimate upper bounds of angular deviations with respect to expected errors in image irradiances. Such predictions are necessary for the practical application of the photometric stereo method.
View record details 
An Image Stitcher and Its Application in Panoramic Movie Making
Chen, ChiaYen; Klette, Reinhard (1997)
Report
The University of Auckland LibraryYou are granted permission for the noncommercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (fortyfive) days from the most recent time that you verified that this technical report is still available from the original CITR web site; http://citr.auckland.ac.nz/techreports/ under terms that include this permission. All other rights are reserved by the author(s). This paper describes the design and implementation of an image stitcher which can be used to join colour images. The images are joined in two steps. The first step involves registering two adjacent images using a minimum absolute difference method. The second step adjusts the contrast of the joined images using a linear interpolation of the intensity difference between the two images. The images joined by the stitcher can be used in many applications, such as panoramic viewing, architectural walk through and other teaching or researching purposes.
View record details