2022-01-24T13:00:26Zhttps://researchspace.auckland.ac.nz/dspace-oai/requestoai:researchspace.auckland.ac.nz:2292/36552012-02-02T23:23:15Zcom_2292_122col_2292_3508
Antoniou, I
Calude, C.S
Dinneen, M.J
2009-04-16T23:16:50Z
2009-04-16T23:16:50Z
2000-11
CDMTCS Research Reports CDMTCS-147 (2000)
1178-3540
http://hdl.handle.net/2292/3655
These are additional papers of talks that were presented at the Second International
Conference on Unconventional Models of Computation (UMC’2K).
UMC’2K, organized by the Centre for Discrete Mathematics and Theoretical
Computer Science, the International Solvay Institutes for Physics and Chemistry
and the Vrije Universiteit Brussel Theoretical Physics Division was held
at Solvay Institutes during December 13–16, 2000.
The conference encompasses all areas of unconventional computation, especially
quantum computing, DNA-based computation, evolutionary algorithms
and other proposals for computation models that go beyond the Turing model.
Additional refereed and invited papers of UMC’2K appear in the following proceedings:
I. Antoniou, C. S. Calude, M. J. Dinneen, editors. Unconventional
Models of Computation, UMC’2K, Springer-Verlag, London, December
2000, XI + 301 pages.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Supplemental Papers for the 2nd Unconventional Models of Computation Conference
Technical Report
oai:researchspace.auckland.ac.nz:2292/38242012-02-02T23:23:18Zcom_2292_122col_2292_3508
Calude, C.S
Zimand, M
2009-04-16T23:17:10Z
2009-04-16T23:17:10Z
2008-01
CDMTCS Research Reports CDMTCS-317 (2008)
1178-3540
http://hdl.handle.net/2292/3824
Two objects are independent if they do not a ect each other. Independence is wellunderstood
in classical information theory, but less in algorithmic information theory.
Working in the framework of algorithmic information theory, the paper proposes two
types of independence for arbitrary in nite binary sequences and studies their properties.
Our two proposed notions of independence have some of the intuitive properties
that one naturally expects. For example, for every sequence x, the set of sequences
that are independent with x has measure one. For both notions of independence we investigate
to what extent pairs of independent sequences, can be e ectively constructed
via Turing reductions (from one or more input sequences). In this respect, we prove
several impossibility results. For example, it is shown that there is no e ective way of
producing from an arbitrary sequence with positive constructive Hausdor dimension
two sequences that are independent (even in the weaker type of independence) and
have super-logarithmic complexity. Finally, a few conjectures and open questions are
discussed.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Algorithmically Independent Sequences
Technical Report
oai:researchspace.auckland.ac.nz:2292/278532016-04-22T14:17:15Zcom_2292_122col_2292_3508
Hoffmann, S
Staiger, L
2016-01-04T21:55:58Z
2016-01-04T21:55:58Z
2015
CDMTCS Research Reports CDMTCS-484 (2015)
1178-3540
http://hdl.handle.net/2292/27853
The space of one-sided infinite words plays a crucial rôle in several parts of Theoretical Computer Science. Usually, it is convenient to regard this space as a metric space, the Cantor-space. It turned out that for several
purposes topologies other than the one of the Cantor-space are useful, e.g. for studying fragments of first-order logic over infinite words or for a topological characterisation of random infinite words.
Continuing the work of [SS10], here we consider two different refinements of the Cantor-space, given by measuring common factors, and common factors occurring infinitely often. In particular we investigate the relation of these topologies to the sets of infinite words definable by finite automata, that is, to regular !-languages.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Subword Metrics for Infinite Words
Technical Report
oai:researchspace.auckland.ac.nz:2292/35732012-02-02T23:23:16Zcom_2292_122col_2292_3508
Hertling, P
2009-04-16T23:09:52Z
2009-04-16T23:09:52Z
1997-10
CDMTCS Research Reports CDMTCS-064 (1997)
1178-3540
http://hdl.handle.net/2292/3573
Every infinite binary sequence is Turing reducible to a random one. This is
a corollary of a result of Peter Gacs stating that for every co-r.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 co-r.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.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Surjective Functions on Computably Growing Cantor Sets
Technical Report
oai:researchspace.auckland.ac.nz:2292/374962018-07-21T12:31:16Zcom_2292_122col_2292_3508
Staiger, L
2018-07-18T04:42:51Z
2018-07-18T04:42:51Z
2017
CDMTCS Research Reports CDMTCS-509 (2017)
1178-3540
http://hdl.handle.net/2292/37496
A quasiperiod of a finite or infinite string is a word whose occurrences cover every part of the string. An infinite string is referred to as quasiperiodic if it has a quasiperiod.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Quasiperiods of Infinite Words
Technical Report
oai:researchspace.auckland.ac.nz:2292/37032012-02-02T23:23:15Zcom_2292_122col_2292_3508
Calude, C.S
Dinneen, Michael
Peper, F
2009-04-16T23:15:44Z
2009-04-16T23:15:44Z
2002-10
CDMTCS Research Reports CDMTCS-195 (2002)
1178-3540
http://hdl.handle.net/2292/3703
These are additional abstracts of talks that were presented at the Third International Conference on Unconventional Models of Computation (UMC’02). Computer Science, and the Kansai Advanced Research Centre of the Communications Research Laboratory was held at the Orbis hall in the centre of Kobe’s Rokko island, during October 15-19, 2002. The conference encompasses all areas of unconventional computation, especially quantum computing, DNA-based computation, evolutionary algorithms and other proposals for computation models that go beyond the Turing model. Additional refereed and invited papers of UMC’02 appear in the following proceedings: C.S. Calude, M.J. Dinneen, and F. Peper editors. Unconventional Models of Computation, UMC’02, LNCS 2509, Springer-Verlag, October 2002, VIII+300 pages.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Supplemental Papers for the 3nd Unconventional Models of Computation Conference
Technical Report
oai:researchspace.auckland.ac.nz:2292/494842020-01-11T11:36:32Zcom_2292_122col_2292_3508
Staiger, L
2020-01-10T01:36:47Z
2020-01-10T01:36:47Z
2019
CDMTCS Research Reports CDMTCS-535 (2019)
1178-3540
http://hdl.handle.net/2292/49484
Using an iterative tree construction we show that for simple computable
subsets of the Cantor space Hausdorff, constructive and computable
dimensions might be incomputable.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
On the incomputability of computable dimension
Technical Report
oai:researchspace.auckland.ac.nz:2292/36322012-02-02T23:23:16Zcom_2292_122col_2292_3508
Castellanos, J
Paun, G
Rodriguez-Paton, A
2009-04-16T23:17:55Z
2009-04-16T23:17:55Z
2000-02
CDMTCS Research Reports CDMTCS-123 (2000)
1178-3540
http://hdl.handle.net/2292/3632
We consider a combination of P systems with objects described
by symbols with P systems with objects described by strings. Namely, we
work with multisets of strings and consider as the result of a computation
the number of strings in a given output membrane. The strings (also called
worms) are processed by replication, splitting, mutation, and recombination;
no priority among rules and no other ingredient is used. In these circumstances,
it is proved that (1) P systems of this type can generate all recursively
enumerable sets of numbers, and, moreover, (2) the Hamiltonian Path
Problem in a directed graph can be solved in a quadratic time, while the SAT
problem can be solved in a linear time.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Computing with Membranes: P Systems with Worm-Objects
Technical Report
oai:researchspace.auckland.ac.nz:2292/317542017-02-11T11:30:48Zcom_2292_122col_2292_3508
Calude, CS
Thompson, D
2017-02-07T03:37:17Z
2017-02-07T03:37:17Z
2016
CDMTCS Research Reports CDMTCS-497 (2016)
1178-3540
http://hdl.handle.net/2292/31754
Incompleteness and undecidability have been used for many years as arguments against automatising the practice of mathematics.
The advent of powerful computers and proof-assistants – programs that assist the development of formal proofs by human-machine collaboration – has revived the interest in formal proofs and diminished considerably the value of these arguments.
In this paper we discuss some challenges proof-assistants face in handling undecidable problems – the very results cited above – using for illustrations the generic proof-assistant Isabelle.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Incompleteness, Undecidability and Automated Proofs
Technical Report
oai:researchspace.auckland.ac.nz:2292/239072015-01-28T11:38:32Zcom_2292_122col_2292_3508
Calude, CS
Longo, G
2015-01-05T00:14:07Z
2015-01-05T00:14:07Z
2014
CDMTCS Research Reports CDMTCS-474 (2014)
1178-3540
http://hdl.handle.net/2292/23907
In this paper we briefly discuss various forms of randomness that physics, mathematics and computing
have proposed. Classical and quantum physics view randomness, that we describe as unpredictability in
the intended theory, in different ways. Computing allows to discuss this issue in an abstract, yet very expressive
mean, which yields useful hierarchies of randomness and may help to relate its various forms. We introduce then
the open field of biological randomness—its peculiar nature and role in ontogenesis and in evolutionary dynamics
(phylogenesis). Randomness does not oppose, but contributes to the organisms’ and populations’ structural
stability, in contexts where the notion of probability, as measurement of randomness, is not well defined.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Classical, Quantum and Biological Randomness as Relative Incomputability
Technical Report
oai:researchspace.auckland.ac.nz:2292/35892012-02-02T23:23:16Zcom_2292_122col_2292_3508
Dinneen, Michael
Pritchard, G
Wilson, Mark
2009-04-16T23:12:44Z
2009-04-16T23:12:44Z
1998-04
CDMTCS Research Reports CDMTCS-080 (1998)
1178-3540
http://hdl.handle.net/2292/3589
We consider the problem of constructing networks with as many nodes as possible,
subject to upper bounds on the degree and broadcast time. This paper includes the
results of an extensive empirical study of broadcasting in small regular graphs using a stochastic
search algorithm to approximate the broadcast time. Significant improvements on
known results are obtained for cubic broadcast networks.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Degree- and Time- Constrained Broadcast Networks
Technical Report
oai:researchspace.auckland.ac.nz:2292/37682012-02-02T23:23:13Zcom_2292_122col_2292_3508
Calude, C.S
Calude, E
Dinneen, Michael
2009-04-16T23:09:54Z
2009-04-16T23:09:54Z
2005-04
CDMTCS Research Reports CDMTCS-261 (2005)
1178-3540
http://hdl.handle.net/2292/3768
The famous story of the number 1729, the smallest integer which can be expressed
as the sum of two positive cubes in two different ways, motivated the
introduction of Taxicab Numbers. The smallest number expressible as the sum of
two cubes in n different ways is called Taxicab(n). So, Taxicab(2) = 1729. Further
on, Taxicab(5) = 48988659276962496. Computing Taxicab(n) is challenging and
interesting, both from mathematical and programming points of view.
The exact value of Taxicab(6) is not known; in view of the results obtained
by Bernstein [1] and Rathbun [14] it follows that Taxicab(6) is in the interval
[10¹⁸, 24153319581254312065344]. In [5] we proved that with probability greater
than 99%, Taxicab(6) = 24153319581254312065344.
In this note we improve the method used in [5] in two ways: we use (1) a larger,
and (2) a better quality random sampling, namely, a sample of 562,500 quantum
random integers drawn from the above mentioned interval using Quantis, [10]. As a
result, we prove that the above value for Taxicab(6) is true with probability greater
than 99.8%.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
What is the Value of Taxicab(6)? An Update
Technical Report
oai:researchspace.auckland.ac.nz:2292/37522012-02-02T23:23:19Zcom_2292_122col_2292_3508
Harmer, M.
2009-04-16T23:11:55Z
2009-04-16T23:11:55Z
2004-07
CDMTCS Research Reports CDMTCS-245 (2004)
1178-3540
http://hdl.handle.net/2292/3752
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.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Fitting Parameters for a Solvable Model of a Quantum Network (CDMTCS)
Technical Report
oai:researchspace.auckland.ac.nz:2292/105632012-02-09T11:41:41Zcom_2292_122col_2292_3508
Calude, C.S.
Calude, E.
2012-01-16T03:19:45Z
2012-01-16T03:19:45Z
2011
CDMTCS Research Reports CDMTCS-410 (2011)
1178-3540
http://hdl.handle.net/2292/10563
This paper presents on overview of results obtained with an algorithmic
uniform method to measure the complexity of a large class of mathematical
problems and discusses a few open problems.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
The Complexity of Mathematical Problems: An Overview of Results and Open Problems
Technical Report
oai:researchspace.auckland.ac.nz:2292/213502014-05-26T12:33:27Zcom_2292_122col_2292_3508
Tran Le, VB
Link, S
Ferrarotti, F
2014-01-05T22:48:17Z
2014-01-05T22:48:17Z
2013
CDMTCS Research Reports CDMTCS-451 (2013)
1178-3540
http://hdl.handle.net/2292/21350
SQL designs result from methodologies such as UML or Entity-Relationship
models, description logics, or relational normalization. Independently of the methodology, sample data is promoted by academia and industry to visualize and consolidate the designs produced. SQL table definitions are a standard-compliant encoding of their designers' perception about the semantics of an application domain.
Armstrong sample data visualize these perceptions. We present a tool that computes Armstrong samples for different classes of SQL constraints. Exploiting our tool, we then investigate empirically how these Armstrong samples help design
teams recognize domain semantics. New measures empower us to compute the
distance between constraint sets in order to evaluate the usefulness of our tool.
Extensive experiments con rm that users of our tool are likely to recognize domain
semantics they would overlook otherwise. The tool thereby e ffectively complements existing design methodologies in finding quality schemata that process data efficiently.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Effective Recognition and Visualization of Semantic Requirements by Perfect SQL Samples
Technical Report
oai:researchspace.auckland.ac.nz:2292/36982012-02-02T23:23:13Zcom_2292_122col_2292_3508
Goncharov, S.S
Khoussainov, B
2009-04-16T23:17:04Z
2009-04-16T23:17:04Z
2002-05
CDMTCS Research Reports CDMTCS-190 (2002)
1178-3540
http://hdl.handle.net/2292/3698
[no abstract available]
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Complexity of Computable Models
Technical Report
oai:researchspace.auckland.ac.nz:2292/198112013-01-07T11:31:57Zcom_2292_122col_2292_3508
Abbott, A.A
Calude, C.S.
Conder, J.
Svozil, K
2013-01-06T23:09:23Z
2013-01-06T23:09:23Z
2012
CDMTCS Research Reports CDMTCS-422 (2012)
1178-3540
http://hdl.handle.net/2292/19811
We present a stronger variant of the Kochen-Specker theorem in which some quantum observables are identiﬁed to be provably value indeﬁnite. This result is utilised for the construction and certiﬁcation of a dichotomic quantum random number generator operating in a three-dimensional Hilbert space.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Kochen-Specker Theorem Revisited and Strong Incomputability of Quantum Randomness
Technical Report
oai:researchspace.auckland.ac.nz:2292/35692012-02-02T23:23:19Zcom_2292_122col_2292_3508
Calude, E
Lipponen, M
2009-04-16T23:17:33Z
2009-04-16T23:17:33Z
1997-10
CDMTCS Research Reports CDMTCS-060 (1997)
1178-3540
http://hdl.handle.net/2292/3569
We construct a minimal automaton for an output-incomplete Moore automa-
ton. The approach is motivated by physical interpretation of seeing deterministic finite
automata as models for elementary particles. When compared to some classical methods
our minimal automaton is unique up to an isomorphism and preserves also the undefined
or unspecified behaviour of the original automaton.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Minimal Deterministic Incomplete Automata
Technical Report
oai:researchspace.auckland.ac.nz:2292/450752019-01-12T11:31:25Zcom_2292_122col_2292_3508
2019-01-09T02:23:08Z
2019-01-09T02:23:08Z
2018
CDMTCS Research Reports CDMTCS-504 (2018)
1178-3540
http://hdl.handle.net/2292/45075
Proceedings of the Asian Branch of International Conference on Membrane Computing (ACMC2018)
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Proceedings of ACMC 2018
Technical Report
oai:researchspace.auckland.ac.nz:2292/35862012-02-02T23:23:19Zcom_2292_122col_2292_3508
Hertling, P
2009-04-16T23:15:56Z
2009-04-16T23:15:56Z
1998-01
CDMTCS Research Reports CDMTCS-077 (1998)
1178-3540
http://hdl.handle.net/2292/3586
Including the range of a rational function over an interval is an im-
portant problem in numerical computation. A direct interval arithmetic
evaluation of a formula for the function yields in general a superset with
an error linear in the width of the interval. Special formulas like the cen-
tered forms yield a better approximation with a quadratic error. Alefeld
posed the question whether in general there exists a formula whose inter-
val arithmetic evaluation gives an approximation of better than quadratic
order. In this paper we show that the answer to this question is negative
if in the interval arithmetic evaluation of a formula only the basic four
interval operations +,-,•,/= are used.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
A Lower Bound for Range Enclosure in Interval Arithmetic
Technical Report
oai:researchspace.auckland.ac.nz:2292/37752012-02-02T23:23:16Zcom_2292_122col_2292_3508
Greenberger, D.M
Svozil, K
2009-04-16T23:10:48Z
2009-04-16T23:10:48Z
2005-06
CDMTCS Research Reports CDMTCS-268 (2005)
1178-3540
http://hdl.handle.net/2292/3775
We introduce a quantum mechanical model of time travel which includes two figurative beam splitters in
order to induce feedback to earlier times. This leads to a unique solution to the paradox where one could kill
one’s grandfather in that once the future has unfolded, it cannot change the past, and so the past becomes
deterministic. On the other hand, looking forwards towards the future is completely probabilistic. This
resolves the classical paradox in a philosophically satisfying manner.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Quantum Theory Looks at Time Travel
Technical Report
oai:researchspace.auckland.ac.nz:2292/37302012-02-02T23:23:16Zcom_2292_122col_2292_3508
Arulanandham, J.J
Calude, C.S
Dinneen, Michael
2009-04-16T23:18:04Z
2009-04-16T23:18:04Z
2003-10
CDMTCS Research Reports CDMTCS-223 (2003)
1178-3540
http://hdl.handle.net/2292/3730
We propose a natural computational model called a balance machine. The computational model consists of components that resemble ordinary physical balances, each with an intrinsic property to automatically balance the weights on their left, right pans. If we start with certain fixed weights (representing inputs) on some of the pans, then the balance-like components would vigorously try to balance themselves by filling the rest of the pans with suitable weights (representing the outputs). This balancing act can be viewed as a computation. We will show that the model allows us to construct those primitive (hardware) components that serve as the building blocks of a general purpose (universal) digital computer: logic gates, memory cells (flip-flops), and transmission lines. One of the key features of the balance machine is its “bidirectional” operation: both a function and its (partial) inverse can be computed spontaneously using the same machine. Some practical applications of the model are discussed.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Balance Machines: Computing = Balancing
Technical Report
oai:researchspace.auckland.ac.nz:2292/35132012-02-02T23:23:16Zcom_2292_122col_2292_3508
Hafner, P.R
2009-04-16T23:16:00Z
2009-04-16T23:16:00Z
1995-06
CDMTCS Research Reports CDMTCS-004 (1995)
1178-3540
http://hdl.handle.net/2292/3513
We review the status of the Degree/Diameter problem for both,
graphs and digraphs and present new Cayley digraphs which yield improvements over some of the previously known largest vertex transitive digraphs of
given degree and diameter.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Large Cayley Graphs and Digraphs with Small Degree and Diameter
Technical Report
oai:researchspace.auckland.ac.nz:2292/38042012-02-02T23:23:18Zcom_2292_122col_2292_3508
Hay, N.J
Shorin, A
Wang, J
2009-04-16T23:14:31Z
2009-04-16T23:14:31Z
2007-01
CDMTCS Research Reports CDMTCS-297 (2007)
1178-3540
http://hdl.handle.net/2292/3804
This booklet contains the proceedings of the First University of Auckland Computer
Science Graduate Workshop (UACSGSW’06) held on Friday, 8 September 2006.
TheWorkshop, the first of its kind in our department, offers graduate students a chance
to present their research to an audience including computer science and information technology
graduate students, academics and industry representatives. The participants are
MSc, Honours, PGDipSci, PhD, MEng and stage-4 BE project students in computer science
and related areas. All submissions have been refereed.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
University of Auckland Computer Science Graduate Workshop 2006
Technical Report
oai:researchspace.auckland.ac.nz:2292/450692019-01-12T11:31:30Zcom_2292_122col_2292_3508
Yao, P
Hua, R
2019-01-09T02:23:04Z
2019-01-09T02:23:04Z
2018
CDMTCS Research Reports CDMTCS-523 (2018)
1178-3540
http://hdl.handle.net/2292/45069
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The authors
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Finding Maximum-sized Native Clique Embeddings: Implementing and Extending the Block Clique Embedding Algorithm
Technical Report
oai:researchspace.auckland.ac.nz:2292/105542012-02-09T11:41:47Zcom_2292_122col_2292_3508
Gimel'farb, G.
Nicolescu, R.
Ragavan, S.
2012-01-16T03:19:44Z
2012-01-16T03:19:44Z
2011
CDMTCS Research Reports CDMTCS-401 (2011)
1178-3540
http://hdl.handle.net/2292/10554
Designing parallel versions of sequential algorithms has attracted renewed attention, due to recent hardware advances, including various general-purpose multi-core and many-core processors, as well as special-purpose FPGA implementations. P systems consist of networks of autonomous cells, such that each cell transforms
its input signals in accord with its symbol-rewriting rules and feeds the output results into its immediate neighbours. Inherent massive intra- and inter-cell parallelisms make P systems a prospective theoretical testbed for designing efficient parallel and parallel-sequential algorithms. This paper discusses the ability of P
systems to implement the symmetric dynamic programming stereo (SDPS) matching algorithm, which explicitly accounts for binocular or monocular visibility of 3D surface points. Given enough cells, the P system implementation speeds up the inner algorithm loop from O(nd) to O(n + d), where n is the width of a stereo
image and d is the disparity range. The implementation also gives an insight into
to a more general SDPS algorithm that allows a possible multiplicity of solutions
to the ill-posed optimal stereo matching problem.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
P Systems in Stereo Matching (extended version)
Technical Report
oai:researchspace.auckland.ac.nz:2292/37932012-02-02T23:23:16Zcom_2292_122col_2292_3508
Speidel, U
2009-04-16T23:10:05Z
2009-04-16T23:10:05Z
2006-10
CDMTCS Research Reports CDMTCS-286 (2006)
1178-3540
http://hdl.handle.net/2292/3793
This paper describes the derivation of the T-complexity and T-in-
formation theory from the decomposition of finite strings, based on the
duality of strings and variable-length T-codes. It further outlines its similarity to the string parsing algorithm by Lempel and Ziv. In its first
version [15], it was intended as a summary of work published mainly by
Titchener and Nicolescu. Apart from minor corrections, the present extended version incorporates feedback from previous readers and presents
new results obtained since.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
T-Complexity and T-Information Theory--an Executive Summary, 2nd revised version
Technical Report
oai:researchspace.auckland.ac.nz:2292/213442014-05-26T12:34:18Zcom_2292_122col_2292_3508
Nies, A
2014-01-05T22:48:16Z
2014-01-05T22:48:16Z
2013
CDMTCS Research Reports CDMTCS-445 (2013)
1178-3540
http://hdl.handle.net/2292/21344
Cost functions were introduced as a framework for constructions
of c.e. incomputable sets that are close to computable. We
carry out a systematic study of cost functions. We relate their algebraic
properties to their expressive strength. We show that additive cost functions
correspond to the K-trivial sets. We prove a cost function basis
theorem, and give a general construction for building c.e. sets that are
close to being Turing complete.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Calculus of Cost Functions
Technical Report
oai:researchspace.auckland.ac.nz:2292/198072013-01-07T11:31:32Zcom_2292_122col_2292_3508
Hertel, J
2013-01-06T23:09:22Z
2013-01-06T23:09:22Z
2012
CDMTCS Research Reports CDMTCS-418 (2012)
1178-3540
http://hdl.handle.net/2292/19807
We use the recently introduced [1,2] inductive complexity measure to
evaluate the inductive complexity of Goodstein's Theorem, a statement that is
independent from Peano Arithmetic.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Inductive Complexity of Goodstein's Theorem
Technical Report
oai:researchspace.auckland.ac.nz:2292/238882016-04-22T12:35:16Zcom_2292_122col_2292_3508
Böttcher, S
Link, S
Zhang, L
2015-01-05T00:14:03Z
2015-01-05T00:14:03Z
2014
CDMTCS Research Reports CDMTCS-453 (2014)
1178-3540
http://hdl.handle.net/2292/23888
We present LECQTER, a system for learning how to write sound conjunctive SQL
queries by example. The key novelty of LECQTER is its ability to construct for every
given conjunctive query Q without self-joins over every given database schema,
a database dbQ such that for every query Q'
in a large fragment of conjunctive
queries, Q and Q' produce matching answers on every database if and only if Q
and Q′ produce matching answers on dbQ. Since it is known that such construction
is impossible to achieve under set semantics, the key novelty relies on the use
of SQL’s bag semantics. LECQTER shows the answer to both the user query Q'
and the target query Q, such that users receive immediate feedback that either
their query is correct - and not just their query answer - or where their query
answer deviates from that of the target query. LECQTER can therefore automate
feedback and assessment in its primary application area of Massive Open Online
Courses. Everyone who requires basic SQL skills to match the demands of our
data-centric society can use LECQTER to confidently learn how to write sound
conjunctive queries under the semantics of the industry standard.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
LECQTER: Learning Conjunctive SQL Queries Through Exemplars
Technical Report
oai:researchspace.auckland.ac.nz:2292/35932012-02-02T23:23:18Zcom_2292_122col_2292_3508
Calude, C.S
Dinneen, Michael
2009-04-16T23:10:18Z
2009-04-16T23:10:18Z
1998-05
CDMTCS Research Reports CDMTCS-084 (1998)
1178-3540
http://hdl.handle.net/2292/3593
Is there any limit to discrete computation, and more generally, to scientific knowledge? This is one of the problems studied by the Centre for Discrete Mathematics and
Theoretical Computer Science of the University of Auckland.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Breaking the Turing Barrier
Technical Report
oai:researchspace.auckland.ac.nz:2292/36592012-02-02T23:23:17Zcom_2292_122col_2292_3508
Bodlaender, H.L
Dinneen, Michael
Khoussainov, B
2009-04-16T23:13:16Z
2009-04-16T23:13:16Z
2001-04
CDMTCS Research Reports CDMTCS-151 (2001)
1178-3540
http://hdl.handle.net/2292/3659
In this paper, we study the complexity of deciding which player has a
winning strategy in certain types of McNaughton games. These graph games can be
used as models for computational problems and processes of infinite duration. We
consider the cases (1) where the first player wins when vertices in a specified set are
visited infinitely often and vertices in another specified set are visited finitely often, (2)
where the first player wins when exactly those vertices in one of a number of specified
disjoint sets are visited infinitely often, and (3) a generalization of these first two cases.
We give polynomial time algorithms to determine which player has a winning strategy
in each of the games considered.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
On Game-Theoretic Models of Networks
Technical Report
oai:researchspace.auckland.ac.nz:2292/36752012-02-02T23:23:16Zcom_2292_122col_2292_3508
Calude, C.S
Dinneen, Michael
Shu, C.-K
2009-04-16T23:15:09Z
2009-04-16T23:15:09Z
2001-12
CDMTCS Research Reports CDMTCS-167 (2001)
1178-3540
http://hdl.handle.net/2292/3675
A Chaitin Omega number is the halting probability of a universal Chaitin (selfdelimiting
Turing) machine. Every Omega number is both computably enumerable
(the limit of a computable, increasing, converging sequence of rationals) and random
(its binary expansion is an algorithmic random sequence). In particular, every
Omega number is strongly non-computable. The aim of this paper is to describe a
procedure, which combines Java programming and mathematical proofs, for computing
the exact values of the first 63 bits of a Chaitin Omega:
000000100000010000100000100001110111001100100111100010010011100.
Full description of programs and proofs will be given elsewhere.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Computing a Glimpse of Randomness
Technical Report
oai:researchspace.auckland.ac.nz:2292/213472014-05-26T12:33:53Zcom_2292_122col_2292_3508
Calude,CS
Staiger, L
2014-01-05T22:48:17Z
2014-01-05T22:48:17Z
2013
CDMTCS Research Reports CDMTCS-448 (2013)
1178-3540
http://hdl.handle.net/2292/21347
We present a systematic comparison between Liouville, computable, Borel normal and Martin-Lof random numbers. The nine non-empty combinations, all small in measure
or category, are illustrated with concrete examples. The sets of Liouville numbers
and Martin-Lof random numbers are disjoint, thus showing that the irrationality exponent is not a measure of randomness. Finally, we construct the first computable set of correlations appearing in every Martin-Lof random number, but not in all numbers.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Liouville Numbers, Borel Normality and Algorithmic Randomness
Technical Report
oai:researchspace.auckland.ac.nz:2292/37852012-02-02T23:23:14Zcom_2292_122col_2292_3508
Schwarz, S
2009-04-16T23:16:21Z
2009-04-16T23:16:21Z
2006-05
CDMTCS Research Reports CDMTCS-278 (2006)
1178-3540
http://hdl.handle.net/2292/3785
We connect Lukasiewicz logic, a well-established many-valued logic, with
weighted logics, recently introduced by Droste and Gastin. We use this connection
to show that for formal series with coefficients in semirings derived from MValgebras,
recognizability and definability in a fragment of second order Lukasiewicz
logic coincide.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Lukasiewicz Logics and Weighted Logics over MV-Semirings
Technical Report
oai:researchspace.auckland.ac.nz:2292/35662012-02-02T23:23:15Zcom_2292_122col_2292_3508
Hertling, P
2009-04-16T23:13:33Z
2009-04-16T23:13:33Z
1997-09
CDMTCS Research Reports CDMTCS-057 (1997)
1178-3540
http://hdl.handle.net/2292/3566
On countable structures computability is usually introduced via numberings. For
uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable
equivalence there is one and only one equivalence class of representations of the real
numbers which make the basic operations computable. This characterizes the real
numbers in terms of the theory of effective algebras or computable structures, and is
reflected by observations made in real number computer arithmetic. We also give further evidence for the well-known non-appropriateness of the representation to some
base b by proving that strictly less functions are computable with respect to these
representations than with respect to a standard representation of the real numbers.
Furthermore we consider basic constructions of representations and the countable
substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to
a numbering and effectivity with respect to a representation. Special attention is paid
to the countable structure of the computable real numbers.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
The Real Number Structure is Effectively Categorical
Technical Report
oai:researchspace.auckland.ac.nz:2292/38262012-02-02T23:23:19Zcom_2292_122col_2292_3508
Svozil, K
2009-04-16T23:16:54Z
2009-04-16T23:16:54Z
2008-04
CDMTCS Research Reports CDMTCS-319 (2008)
1178-3540
http://hdl.handle.net/2292/3826
Aesthetics, among other criteria, can be statistically examined in terms of the complexity
required for creating and decrypting a work of art. We propose three laws of aesthetic
complexity. According to the first law of aesthetic complexity, too condensed encoding
makes a decryption of a work of art impossible and is perceived as chaotic by the untrained
mind, whereas too regular structures are perceived as monotonous, too orderly and not very
stimulating. Thus a necessary condition for an artistic form or design to appear appealing
is its complexity to lie within a bracket between monotony and chaos. According to the
second law of aesthetic complexity, due to human predisposition, this bracket is invariably
based on natural forms; with rather limited plasticity. The third law of aesthetic complexity
states that aesthetic complexity trends are dominated by the available resources, and thus
also by cost and scarcity.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Aesthetic Complexity
Technical Report
oai:researchspace.auckland.ac.nz:2292/37742012-02-02T23:23:13Zcom_2292_122col_2292_3508
Titchener, M.R
Speidel, U
Yang, J
2009-04-16T23:10:02Z
2009-04-16T23:10:02Z
2005-05
CDMTCS Research Reports CDMTCS-267 (2005)
1178-3540
http://hdl.handle.net/2292/3774
This report compares a variety of computable information measures for finite strings. These include
Shannon’s n-block entropy, the three best known versions of the Lempel-Ziv production complexity
(LZ-76, LZ-77, and LZ-78), and the lesser known T-entropy. We apply these measures to strings of
known entropy, each derived from the logistic map. Pesin’s identity allows us to deduce corresponding
Shannon entropies (Kolmogorov-Sinai entropies) for the sample strings, without resorting to probabilistic
methods.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
A Comparison of Practical Information Measures
Technical Report
oai:researchspace.auckland.ac.nz:2292/450762020-11-24T07:44:23Zcom_2292_122col_2292_3508
Anuradha Mahasinghe, MJD
Dinneen, Michael
Liu, K
2019-01-09T02:51:34Z
2018-02
CDMTCS Research Reports CDMTCS-519 (2018)
1178-3540
http://hdl.handle.net/2292/45076
In this paper we demonstrate how to solve the chromatic sum problem using a D-Wave quantum computer. Starting from a BIP (binary integer programming) formulation, we develop a D-Wave feasible QUBO quadratic unconstrained binary optimisation) formulation of the chromatic sum problem. Our construction requires nk qubits for a graph of n vertices and upper bound of k colours. Further, we present the experimental results obtained by running several QUBOs on a D-Wave quantum computer.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The authors
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Finding the Chromatic Sums of Graphs Using a D-Wave Quantum Computer
Report
oai:researchspace.auckland.ac.nz:2292/37482012-02-02T23:23:17Zcom_2292_122col_2292_3508
Calude, C.S
Juergensen, H
2009-04-16T23:11:36Z
2009-04-16T23:11:36Z
2004-06
CDMTCS Research Reports CDMTCS-241 (2004)
1178-3540
http://hdl.handle.net/2292/3748
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.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Is Complexity a Source of Incompleteness?
Technical Report
oai:researchspace.auckland.ac.nz:2292/450732019-01-12T11:31:32Zcom_2292_122col_2292_3508
Calude, CS
Svozil, K.
2019-01-09T02:23:07Z
2019-01-09T02:23:07Z
2018
CDMTCS Research Reports CDMTCS-528 (2018)
1178-3540
http://hdl.handle.net/2292/45073
We study some aspects of the emergence of l´ogos from x´aos on a simple model of the universe using methods and techniques from algorithmic information and Ramsey theories. Thereby an intrinsic and unusual mixture of meaningful and (spurious) emerging laws surfaces. The emergent laws outnumber the meaningful ones, a picture which is compatible with the lawfulness hypothesis. In accord with the ancient Greek theogony one could say that l´ogos, the Gods and the laws of the universe, originate from “the void,” or from x´aos.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Spurious, Emergent Laws in Number Worlds
Technical Report
oai:researchspace.auckland.ac.nz:2292/36242012-02-02T23:23:13Zcom_2292_122col_2292_3508
Kapoulas, G
2009-04-16T23:09:59Z
2009-04-16T23:09:59Z
1999-11
CDMTCS Research Reports CDMTCS-115 (1999)
1178-3540
http://hdl.handle.net/2292/3624
In the present work the notion of the computable (primitive recursive,
polynomially time computable) p-adic number is introduced and studied. Basic properties
of these numbers and the set of indices representing them are established and it
is proved that the above defined fields are p-adically closed. Using the notion of a notation
system introduced by Y. Moschovakis an abstract characterization of the indices
representing the field of computable p-adic numbers is established.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Computable $p$-adic Numbers
Technical Report
oai:researchspace.auckland.ac.nz:2292/36642012-02-02T23:23:13Zcom_2292_122col_2292_3508
Calude, C.S
Pavlov, B
2009-04-16T23:13:43Z
2009-04-16T23:13:43Z
2001-06
CDMTCS Research Reports CDMTCS-156 (2001)
1178-3540
http://hdl.handle.net/2292/3664
For over fifty years the Turing machine model of computation has defined what it means to “compute”
something; the foundations of the modern theory of computing are based on it. Computers are reading
text, recognizing speech, and robots are driving themselves across Mars. Yet this exponential race will
not produce solutions to many intractable/undecidable problems. Are there alternatives? Quantum
computing offers one realistic alternative (see [8,10,2]). To date, quantum computing has been very
successful in “beating” Turing machines in the race of solving intractable problems, with Shor and
Grover algorithms achieving the most impressive successes. Is there any hope for quantum computing
to challenge the Turing barrier, i.e. to solve an undecidable problem, to compute an uncomputable
function? See Feynman’s argument (see [6], a paper reproduced also in [7]),regarding the possibility of
simulating a quantum system on a (probabilistic) Turing machine.1 simulation.
The current paper discusses solutions of a few simple problems, which suggest that quantum computing
might be capable of computing uncomputable functions. In what follows a “silicon” solution is a
solution tailored for a silicon (classical) computer; a “quantum” solution is a solution designed to work
on a quantum computer.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Coins, Quantum Measurements, and Turing's Barrier: Preliminary Version
Technical Report
oai:researchspace.auckland.ac.nz:2292/198162013-01-07T11:31:49Zcom_2292_122col_2292_3508
Ferrarotti, F.
Hartmann, S.
Link, S.
2013-01-06T23:09:23Z
2013-01-06T23:09:23Z
2012
CDMTCS Research Reports CDMTCS-427 (2012)
1178-3540
http://hdl.handle.net/2292/19816
XML has gained widespread acceptance as a premier format for publishing,
sharing and manipulating data through the web. While the semi-structured nature of XML provides a high degree of syntactic ﬂexibility there are signiﬁcant
shortcomings when it comes to specifying the semantics of XML data. For the
advancement of XML applications it is therefore a major challenge to discover natural classes of constraints that can be utilized effectively by XML data engineers.
This endeavor is ambitious given the multitude of intractability results that have
been established. We investigate a class of XML cardinality constraints that is
precious in the sense that it keeps the right balance between expressiveness and
efficiency of maintenance. In particular, we characterize the associated implication problem axiomatically and develop a low-degree polynomial time algorithm
that can be readily applied for deciding implication. Our class of constraints is
chosen near-optimal as already minor extensions of its expressiveness cause potential intractability. Finally, we transfer our ﬁndings to establish a precious class of soft cardinality constraints on XML data. Soft cardinality constraints need to
be satisﬁed on average only, and thus permit violations in a controlled manner.
Soft constraints are therefore able to tolerate exceptions that frequently occur in
practice, yet can be reasoned about efficiently.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Efficiency Frontiers of XML Cardinality Constraints
Technical Report
oai:researchspace.auckland.ac.nz:2292/35762012-02-02T23:23:18Zcom_2292_122col_2292_3508
Hertling, P
2009-04-16T23:17:23Z
2009-04-16T23:17:23Z
1997-11
CDMTCS Research Reports CDMTCS-067 (1997)
1178-3540
http://hdl.handle.net/2292/3576
The main results of the paper are two effective versions of the Riemann mapping theorem. The first, uniform version is based on the constructive proof of the Riemann mapping
theorem by Bishop and Bridges and formulated in the computability framework developed
by Kreitz and Weihrauch. It states which topological information precisely one needs about
a nonempty, proper, open, connected, and simply connected subset of the complex plane
in order to compute a description of a holomorphic bijection from this set onto the unit
disk, and vice versa, which topological information about the set can be obtained from a
description of a holomorphic bijection. The second version, which is derived from the first
by considering the sets and the functions with computable descriptions, characterizes the
subsets of the complex plane for which there exists a computable holomorphic bijection onto
the unit disk. This solves a problem posed by Pour-El and Richards. We also show that
this class of sets is strictly larger than a class of sets considered by Zhou, which solves an
open problem posed by him. In preparation, recursively enumerable open subsets and closed
subsets of Euclidean spaces are considered and several effective results in complex analysis
are proved.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
The Effective Riemann Mapping Theorem
Technical Report
oai:researchspace.auckland.ac.nz:2292/238892016-04-22T12:34:05Zcom_2292_122col_2292_3508
Hartmann, S
Link, S
2015-01-05T00:14:03Z
2015-01-05T00:14:03Z
2014
CDMTCS Research Reports CDMTCS-454 (2014)
1178-3540
http://hdl.handle.net/2292/23889
The data deluge is defined by increasing amounts of large data with increasing degree
of uncertainty. In a recent response, probabilistic databases are receiving a great deal of
interest from research and industry. One popular approach to probabilistic databases is to
extend traditional relational database technology to handle uncertainty. In this approach
probabilistic databases are probability distributions over a collection of possible worlds of
relational databases. On the one hand, research has seen various efforts to extend query
evaluation from relational to probabilistic databases. On the other hand, updates have
not received much attention at all. In this paper we show that well-known syntactic normal
form conditions capture probabilistic databases with desirable update behavior. Such
behavior includes the absence of data redundancy, insertion, deletion, and modification
anomalies. We further show that standard normalization procedures can be applied to
standard representations of probabilistic databases to obtain database schemata that satisfy
the normal form condition, and can thus be updated efficiently.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Normal Forms and Normalization for Probabilistic Databases under Sharp Constraints
Technical Report
oai:researchspace.auckland.ac.nz:2292/36182012-02-02T23:23:17Zcom_2292_122col_2292_3508
Calude, C.S
Calude, E
Chiou, T
Dumitrescu, M
Nicolescu, Radu
2009-04-16T23:18:43Z
2009-04-16T23:18:43Z
1999-07
CDMTCS Research Reports CDMTCS-109 (1999)
1178-3540
http://hdl.handle.net/2292/3618
Mermin [15] described a simple device to explain Einstein-Podolsky-Rosen (EPR) [12]
correlations. This device was studied by means of a class of probabilistic (Mermin) automata
in [4]. In [5] one shows that every deterministic automaton simulating with confidence 1/2 a
probabilistic Mermin automaton features a classical behaviour. Is the above result true when
the simulation is done at higher levels of confidence? To answer this question we study the
distribution of two computational complementarity principles for two classes of deterministic
automata which mimic the behaviour of Mermin's device with confidence in the intervals
(1/2, 11/16] and (11/16, 7/8]. Since the class of automata to be studied is large, it contains
918≈ 150 ∙10 ¹⁵ elements, we use simulation techniques. We show that, statistically, at any
level of confidence α Є (1/2, 11/16], the class of deterministic automata simulating Mermin
probabilistic automata display less correlations than typical deterministic automata with 9
states and 7 outputs, but at higher levels of confidence α Є (11/16, 7/8], when the simulation
is more accurate, deterministic automata simulating Mermin probabilistic automata display
more correlations than typical deterministic automata with 9 states and 2 outputs. In the
last case, EPR correlations established in [4] for Mermin probabilistic automata correspond to
computational complementarity of the deterministic automata simulating Mermin probabilistic
automata, [10, 13, 18, 3, 6].
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Testing Computational Complementarity for Mermin Automata
Technical Report
oai:researchspace.auckland.ac.nz:2292/213512014-05-26T12:32:52Zcom_2292_122col_2292_3508
Köhler, H
Leck, U
Link, S
2014-01-05T22:48:18Z
2014-01-05T22:48:18Z
2013
CDMTCS Research Reports CDMTCS-452 (2013)
1178-3540
http://hdl.handle.net/2292/21351
In standard SQL database management systems primary key columns are NOT
NULL by default. While NULL columns may be included in unique constraints,
such constraints only ensure uniqueness for tuples which do not feature any null
marker occurrences in the columns involved, and do not fulfil the same function
as primary keys. In this work we investigate the notions of possible and certain
keys, which are intuitive and differ only in their treatment of null markers. It
turns out that possible keys capture the unique constraint of SQL, while certain
keys extend primary keys to include NULL columns, and can be used for similar
purposes. In addition to basic characterization, axiomatization, and simple discovery
approaches for possible and certain keys, we investigate the existence and
construction of Armstrong tables, extremal set problems, and describe an indexing
scheme for enforcing certain keys. Our experiments show that certain keys with
NULLs do occur in real-world databases, and that related computational problems
can be solved efficiently. Certain keys are semantically well-founded, achieve the
goal of Codd’s entity integrity rule and offer more flexibility for data entry than
primary keys.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Possible and Certain SQL Keys
Technical Report
oai:researchspace.auckland.ac.nz:2292/198172013-01-07T11:31:57Zcom_2292_122col_2292_3508
Link, S
2013-01-06T23:09:23Z
2013-01-06T23:09:23Z
2012
CDMTCS Research Reports CDMTCS-428 (2012)
1178-3540
http://hdl.handle.net/2292/19817
Knowledge about complex events is usually incomplete in practice. Zeros can
be utilized to capture such events within probability models. In this article, Geiger
and Pearl’s conditional probabilistic independence statements are investigated in
the presence of zeros. Random variables can be speciﬁed to be zero-free, i.e., to
disallow zeros in their domains. Zero-free random variables provide an effective
mechanism to control the degree of uncertainty caused by permitting zeros. A
ﬁnite axiomatization for the implication problem of saturated conditional independence statements is established under controlled uncertainty, relative to discrete
probability measures. The completeness proof utilizes special probability models
where two events have probability one half. The special probability models enable us to establish an equivalence between the implication problem and that of a
propositional fragment in Cadoli and Schaerf’s S-3 logic. Here, the propositional
variables in S correspond to the random variables speciﬁed to be zero-free. The
duality leads to an almost linear time algorithm to decide implication. It is shown
that this duality cannot be extended to cover general conditional independence
statements. All results subsume classical reasoning about saturated conditional
independence statements as the idealized special case where every random variable
is zero-free. In the presence of controlled uncertainty, zero-free random variables
allow us to soundly approximate classical reasoning about saturated conditional
independence statements.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Sound Approximate Reasoning about Saturated Conditional Probabilistic Independence under Controlled Uncertainty
Technical Report
oai:researchspace.auckland.ac.nz:2292/317552017-02-11T11:30:40Zcom_2292_122col_2292_3508
Bailey, DH
Borwein, JM
2017-02-07T03:37:17Z
2017-02-07T03:37:17Z
2016
CDMTCS Research Reports CDMTCS-498 (2016)
1178-3540
http://hdl.handle.net/2292/31755
Modern computational mathematics requires a philosophical perspective largely at odds with that of traditional mathematics, since current computational mathematics (as distinct from computer science) is by its very nature is discrete, not continuous, and tied to the real world in ways that the more theoretical branches of mathematics (and computer science) often are not. Indeed, computational mathematics provides a means to escape the trap feared by John von Neumann when he wrote,
[T]here is a grave danger that the subject [of mathematics] will develop along the line of least resistance, that the stream so far from its source [in empirical reality] will separate into a multitude of insignificant branches, and that the discipline will become a disorganized mass of details and complexities.
But even a computational approach to mathematics has limits, not the least of which are the uncertainties of errors in hardware, software and algorithms that inevitably are part-and-parcel with computation, although there are ways to limit these uncertainties.
In our chapter, bulwarked by concrete examples, we will try to situate past, present and future mathematical views of space, time, infinity and certainty within a computational context in which, for example, error due to quantum effects begins to compete with traditional
sources of logical and numerical inaccuracy. We shall also argue that traditional taxonomies of complexity and completeness are not only outmoded but actually destructive of progress.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
A Computational Mathematics View of Space, Time and Complexity
Technical Report
oai:researchspace.auckland.ac.nz:2292/528122020-11-24T07:44:24Zcom_2292_122col_2292_3508
Nicolescu, Radu
Henderson, Alec
Dinneen, Michael
2020-09-13T22:33:16Z
2020-09-13T22:33:16Z
2020-07-15
CDMTCS Research Reports CDMTCS-545 (2020)
http://hdl.handle.net/2292/52812
There have been a few NP-hard problems solved using cP systems including the travelling salesman problem. However, these problems are typically in NP rather than higher in the polynomial time hierarchy. In this paper we solve QSAT (also known as TQBF), which is a well-known PSPACE-complete problem. Compared to other extant confluent P systems solutions, our deterministic cP solution only uses a small constant number of custom alphabet symbols (19), a small constant number of rules (10), and a small constant upper-limit of membrane nesting depth (6), independent of the problem size.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The authors
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Solving a PSPACE-complete Problem with cP Systems
Report
oai:researchspace.auckland.ac.nz:2292/35952012-02-02T23:23:15Zcom_2292_122col_2292_3508
Calude, C.S
Merkle, W
Wang, Y
2009-04-16T23:11:04Z
2009-04-16T23:11:04Z
1998-05
CDMTCS Research Reports CDMTCS-086 (1998)
1178-3540
http://hdl.handle.net/2292/3595
The concept of pseudorandomness plays an important role in cryptography. In this note we contrast the notions of complexity-theoretic pseudorandom strings (from algorithmic information theory) and pseudorandom strings (from cryptography). For example, we show that we can easily distinguish a complexity-theoretic pseudorandom ensemble from the uniform ensemble. Both notions of pseudorandom strings are uniformly unpredictable; in contrast with pseudorandom strings, complexity-theoretic pseudorandom strings are not polynomial-time unpredictable.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
A Note on Pseudorandom Generators
Technical Report
oai:researchspace.auckland.ac.nz:2292/37702012-02-02T23:23:13Zcom_2292_122col_2292_3508
Pemantle, R
Wilson, Mark
2009-04-16T23:10:13Z
2009-04-16T23:10:13Z
2005-04
CDMTCS Research Reports CDMTCS-263 (2005)
1178-3540
http://hdl.handle.net/2292/3770
The purpose of this paper is to review recent developments in the asymptotics of
multivariate generating functions, and to give an exposition of these that is accessible
and centered around applications. We begin, however, with a brief review of univariate
generating functions and of previous results on multivariate generating functions.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Twenty Combinatorial Examples of Asymptotics Derived From Multivariate Generating Functions
Technical Report
oai:researchspace.auckland.ac.nz:2292/375002018-07-21T12:31:18Zcom_2292_122col_2292_3508
Yanofsky, NS
2018-07-18T04:42:53Z
2018-07-18T04:42:53Z
2017
CDMTCS Research Reports CDMTCS-513 (2017)
1178-3540
http://hdl.handle.net/2292/37500
Theoretical computer science discusses foundational issues about computations. It asks and answers questions such as “What is a computation?”, “What is computable?”, “What is efficiently computable?", "What is information?", "What is random?", "What is an algorithm?", etc. We will present many of the major themes and theorems with the basic language of category theory. Surprisingly, many interesting theorems and concepts of theoretical computer science are easy consequences of functoriality and composition when you look at the right categories and functors connecting them.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Theoretical Computer Science for the Working Category Theorist
Technical Report
oai:researchspace.auckland.ac.nz:2292/37472012-02-02T23:23:13Zcom_2292_122col_2292_3508
Calude, C.S
Campeanu, C
Dumitrescu, M
2009-04-16T23:09:48Z
2009-04-16T23:09:48Z
2004-05
CDMTCS Research Reports CDMTCS-240 (2004)
1178-3540
http://hdl.handle.net/2292/3747
How likely is that a randomly given (non-) deterministic finite automaton recognizes no
word? A quick reflection seems to indicate that not too many finite automata accept no word;
but, can this intuition be confirmed?
In this paper we offer a statistical approach which allows us to conclude that for automata,
with a large enough number of states, the probability that a given (non-) deterministic finite
automaton recognizes no word is close to zero. More precisely, we will show, with a high
degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for
both deterministic and non-deterministic finite automata: a) the probability that an automaton
recognizes no word tends to zero when the number of states and the number of letters in the
alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the
number of letters of the alphabet of the automaton tends to infinity, the probability is strictly
positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and
statistical analysis.
The present analysis shows that for all practical purposes the fraction of automata recognizing
no words tends to zero when the number of states and the number of letters in the alphabet
grow indefinitely.
In the last section we critically discuss the method and result obtained in this paper. From
a theoretical point of view, the result can motivate the search for “certitude”, that is, a proof
of the fact established here in probabilistic terms. In fact, the method used is much more
important than the result itself. The method is “general” in the sense that it can be applied to
a variety of questions in automata theory, certainly some more difficult than the problem solved
in this note.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Automata Recognizing No Words: A Statistical Approach
Technical Report
oai:researchspace.auckland.ac.nz:2292/36972012-02-02T23:23:19Zcom_2292_122col_2292_3508
Khoussainov, B
2009-04-16T23:17:34Z
2009-04-16T23:17:34Z
2002-05
CDMTCS Research Reports CDMTCS-189 (2002)
1178-3540
http://hdl.handle.net/2292/3697
In this paper we consider a class of infinite one player games played on finite
graphs. Our main questions are the following: given a game, how efficient
is it to find whether or not the player wins the game? If the player wins
the game, then how much memory is needed to win the game? For a given
number n, how does the underlying graph look like if the player has a winning
strategy of memory size n?
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Finite State Strategies in One Player McNaughton Games
Technical Report
oai:researchspace.auckland.ac.nz:2292/37382012-02-02T23:23:16Zcom_2292_122col_2292_3508
Svozil, K
2009-04-16T23:16:32Z
2009-04-16T23:16:32Z
2004-01
CDMTCS Research Reports CDMTCS-231 (2004)
1178-3540
http://hdl.handle.net/2292/3738
Operationalizations of quantum (non)contextuality by entangled multipartite states are discussed.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Farewell to Quantum Contextuality?
Technical Report
oai:researchspace.auckland.ac.nz:2292/36342012-02-02T23:23:17Zcom_2292_122col_2292_3508
Khoussainov, B
2009-04-16T23:15:01Z
2009-04-16T23:15:01Z
2000-03
CDMTCS Research Reports CDMTCS-125 (2000)
1178-3540
http://hdl.handle.net/2292/3634
In this paper we show that for any set X C ω there exists a structure
A that has no presentation computable in X such that A2 has a computable
presentation. We also show that there exists a structure A with infinitely many
computable isomorphism types such that A2 has exactly one computable isomorphism
type.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
On Computable Theoretic Properties of Structures and Their Cartesian Products
Technical Report
oai:researchspace.auckland.ac.nz:2292/213362014-05-26T12:39:52Zcom_2292_122col_2292_3508
Probert, A
Dinneen, MJ
2014-01-05T22:48:15Z
2014-01-05T22:48:15Z
2013
CDMTCS Research Reports CDMTCS-437 (2013)
1178-3540
http://hdl.handle.net/2292/21336
In this paper we present an easy-to-use data structure for representing graphs
of bounded branchwidth, called b-parses. Many hard problems that can be represented as graph problems can be more easily solved when a decomposition of the
graph is taken into account. This is particularly true where the input graph can
be seen to be treelike in some form. An example of such a treelike structure is
branch decomposition, were the edges of a graph are arranged as leaves around
a tree and the internal nodes of the tree represent connectivity between subsets
of the edges of the original graph. This is similar in concept to the idea of tree
decomposition which views the input graph vertices as forming a treelike structure of bounded-sized vertex separators. However branch decompositions may be
simpler to work with than tree decompositions for appropriate problems because
of the structure (and possibly smaller width) of the tree that is formed. In this
paper an algebraic representation of branch decompositions (b-parse) is proposed
as an alternative to the t-parse representation for tree decompositions. An application of this data structure to the known hard problems Minimum Vertex Cover
and 3-Coloring is examined. Finally, possible benefits of using b-parses from the
parallelism perspective is given.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Branchwidth, Branch Decompositions and b-parses
Technical Report
oai:researchspace.auckland.ac.nz:2292/35262012-02-02T23:23:14Zcom_2292_122col_2292_3508
Khoussainov, B
2009-04-16T23:11:45Z
2009-04-16T23:11:45Z
1996-08
CDMTCS Research Reports CDMTCS-017 (1996)
1178-3540
http://hdl.handle.net/2292/3526
[no abstract available]
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Randomness, Computability, and Algebraic Specifications
Technical Report
oai:researchspace.auckland.ac.nz:2292/37892012-02-02T23:23:14Zcom_2292_122col_2292_3508
Chaitin, G.J
2009-04-16T23:10:33Z
2009-04-16T23:10:33Z
2006-07
CDMTCS Research Reports CDMTCS-282 (2006)
1178-3540
http://hdl.handle.net/2292/3789
It would be nice to have a mathematical understanding of basic biological concepts
and to be able to prove that life must evolve in very general circumstances.
At present we are far from being able to do this. But I’ll discuss some partial steps
in this direction plus what I regard as a possible future line of attack.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Speculations on Biology, Information and Complexity
Technical Report
oai:researchspace.auckland.ac.nz:2292/37982012-02-02T23:23:15Zcom_2292_122col_2292_3508
Calude, C.S
Svozil, K
2009-04-16T23:14:46Z
2009-04-16T23:14:46Z
2006-11
CDMTCS Research Reports CDMTCS-291 (2006)
1178-3540
http://hdl.handle.net/2292/3798
As computability implies value definiteness, certain sequences of quantum outcomes cannot be
computable.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Quantum Randomness and Value Indefiniteness
Technical Report
oai:researchspace.auckland.ac.nz:2292/38122012-02-02T23:23:18Zcom_2292_122col_2292_3508
Chaitin, G.J
2009-04-16T23:16:07Z
2009-04-16T23:16:07Z
2007-04
CDMTCS Research Reports CDMTCS-305 (2007)
1178-3540
http://hdl.handle.net/2292/3812
Using 1947 work of Post showing that the word problem for semigroups
is unsolvable, we explicitly exhibit an algebraic characterization
of the bits of the halting probability
Ω. Our proof closely follows
a 1978 formulation of Post’s work by M. Davis. The proof is selfcontained
and not very complicated.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
An Algebraic Characterization of the Halting Probability
Technical Report
oai:researchspace.auckland.ac.nz:2292/238932020-03-09T01:54:04Zcom_2292_122col_2292_3508
Hannula, M
Kontinen, J
Link, S
2015-01-05T00:14:04Z
2015-01-05T00:14:04Z
2014
CDMTCS Research Reports CDMTCS-460 (2014)
1178-3540
http://hdl.handle.net/2292/23893
Uniqueness and independence are two fundamental properties of data. Their enforcement
in database systems can lead to higher quality data, faster data service response time,
better data-driven decision making and knowledge discovery from data. The applications
can be effectively unlocked by providing efficient solutions to the underlying implication
problems of keys and independence atoms. Indeed, for the sole class of keys and the
sole class of independence atoms the associated finite and general implication problems
coincide and enjoy simple axiomatizations. However, the situation changes drastically
when keys and independence atoms are combined. We show that the finite and the general
implication problems are already different for keys and unary independence atoms.
Furthermore, we establish a finite axiomatization for the general implication problem, and
show that the finite implication problem does not enjoy a k-ary axiomatization for any k.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
On Independence Atoms and Keys
Technical Report
oai:researchspace.auckland.ac.nz:2292/239022015-01-28T11:39:14Zcom_2292_122col_2292_3508
Khoussainov, B
2015-01-05T00:14:06Z
2015-01-05T00:14:06Z
2014
CDMTCS Research Reports CDMTCS-470 (2014)
1178-3540
http://hdl.handle.net/2292/23902
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
A Quest For Algorithmically Random Infinite Structures, II
Technical Report
oai:researchspace.auckland.ac.nz:2292/37622012-02-02T23:23:17Zcom_2292_122col_2292_3508
Titchener, M.R
Gulliver, A
Nicolescu, Radu
Speidel, U
Staiger, L
2009-04-16T23:18:23Z
2009-04-16T23:18:23Z
2004-12
CDMTCS Research Reports CDMTCS-255 (2004)
1178-3540
http://hdl.handle.net/2292/3762
Lempel and Ziv (1976) proposed a computable string production-complexity. In this paper, our emphasis is on providing the rigorous development, where possible, for the theoretical aspects of a more recent and contrasting measure of string complexity. We derive expressions for complexity bounds subject to certain constraints. We derive and analytic approximation to the upper bound to linearize the complexity measure. The linearized measure enables us to propose an entropy measure, observed elsewhere to correspond closely with the Kolmogorov-Sinai entropy in simple dynamical systems.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Deterministic Complexity and Entropy
Technical Report
oai:researchspace.auckland.ac.nz:2292/105252012-02-09T11:41:57Zcom_2292_122col_2292_3508
Calude, C.S.
Dinneen, M.J.
Dumitrescu, M.
Svozil, K.
2012-01-16T03:19:41Z
2012-01-16T03:19:41Z
2009
CDMTCS Research Reports CDMTCS-372 (2009)
1178-3540
http://hdl.handle.net/2292/10525
Our aim is to experimentally study the possibility of distinguishing between quantum
sources of randomness—recently proved to be theoretically incomputable—and some
well-known computable sources of pseudo-randomness. Incomputability is a necessary,
but not sufficient “symptom” of “true randomness.” We base our experimental approach
on algorithmic information theory which provides characterizations of algorithmic random
sequences in terms of the degrees of incompressibility of their finite prefixes. Algorithmic
random sequences are incomputable, but the converse implication is false. We
have performed tests of randomness on pseudo-random strings (finite sequences) of length
232 generated with software (Mathematica, Maple), which are cyclic (so, strongly computable),
the bits of p, which is computable, but not cyclic, and strings produced by quantum
measurements (with the commercial device Quantis and by the Vienna IQOQI group).
Our empirical tests indicate quantitative differences, some statistically significant, between
computable and incomputable sources of “randomness.”
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
How Random Is Quantum Randomness? (Extended Version)
Technical Report
oai:researchspace.auckland.ac.nz:2292/38282012-02-02T23:23:17Zcom_2292_122col_2292_3508
Teutenberg, J
2009-04-16T23:16:03Z
2009-04-16T23:16:03Z
2008-04
CDMTCS Research Reports CDMTCS-321 (2008)
1178-3540
http://hdl.handle.net/2292/3828
Programming environments do not support ink annotation. Yet,
annotation is the most effective way to actively read and review
a document. This paper describes a tool, CodeAnnotator, which
integrates annotation support inside a programming
development environment (PDE). This tool is designed and
developed to assist programmers in directly annotating on code
within the programming development environment.
Programmers will benefit from a more intuitive interaction
space to record notes and comments just as they would on paper
documents.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Proceedings of the Computer Graduate Workshop 2007
Technical Report
oai:researchspace.auckland.ac.nz:2292/105582012-02-09T11:41:52Zcom_2292_122col_2292_3508
Abbott, A.A.
Bechmann, M.
Calude, C.S.
Sebald, a.
2012-01-16T03:19:44Z
2012-01-16T03:19:44Z
2011
CDMTCS Research Reports CDMTCS-405 (2011)
1178-3540
http://hdl.handle.net/2292/10558
Nuclear magnetic resonance (NMR) has been widely used as a
demonstrative medium for showcasing the ability for quantum
computations to outperform classical ones. A large number of
such experiments performed have been implementations of the
Deutsch-Jozsa algorithm. It is known, however, that in some cases
the Deutsch-Jozsa problem can be solved classically using as
many queries to the black-box as in the quantum solution. In this
paper we describe experiments in which we take the contrasting
approach of using NMR as a classical computing medium, treating
the nuclear spin vectors classically and utilising an alternative
embedding of bits into the physical medium. This allows us to
determine the actual Boolean function computed by the black-box
for the n = 1, 2 cases, as opposed to only the nature (balanced or
constant) as conventional quantum algorithms do. Discussion of
these experiments leads to some clarification of the complications
surrounding the comparison of different quantum algorithms,
particularly black-box type algorithms.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
A Nuclear Magnetic Resonance Implementation of a Classical Deutsch-Jozsa Algorithm
Technical Report
oai:researchspace.auckland.ac.nz:2292/37782013-01-09T04:35:08Zcom_2292_122com_2292_2303col_2292_3508col_2292_2972
Stay, M.A
2009-04-16T23:15:04Z
2009-04-16T23:15:04Z
2005-08
CDMTCS Research Reports CDMTCS-271 (2005)
1178-3540
http://hdl.handle.net/2292/3778
This thesis examines some problems related to Chaitin’s
number. In the first section, we describe
several new minimalist prefix-free machines suitable for the study of concrete algorithmic information
theory; the halting probabilities of these machines are all
numbers. In the second part, we show that
when such a sequence is the result given by a measurement of a system, the system itself can be shown
to satisfy an uncertainty principle equivalent to Heisenberg’s uncertainty principle. This uncertainty
principle also implies Chaitin’s strongest form of incompleteness.
In the last part, we show that
can be written as an infinite product over halting programs; that
there exists a “natural,” or base-free formulation that does not (directly) depend on the alphabet of
the universal prefix-free machine; that Tadaki’s generalized halting probability is well-defined even for
arbitrary univeral Turing machines and the plain complexity; and finally, that the natural generalized
halting probability can be written as an infinite product over primes and has the form of a zeta function
whose zeros encode halting information. We conclude with some speculation about physical systems in
which partial randomness could arise, and identify many open problems.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Truth and Light: Physical Algorithmic Randomness
Technical Report
oai:researchspace.auckland.ac.nz:2292/213342014-05-26T12:40:02Zcom_2292_122col_2292_3508
Tadaki, K
Doi, N
2014-01-05T22:48:15Z
2014-01-05T22:48:15Z
2013
CDMTCS Research Reports CDMTCS-435 (2013)
1178-3540
http://hdl.handle.net/2292/21334
The secure instantiation of the random oracle is one of the major open
problems in modern cryptography. We investigate this problem using concepts and
methods of algorithmic randomness.
In modern cryptography, the random oracle model is widely used as an imaginary
framework in which the security of a cryptographic scheme is discussed. In the random
oracle model, the cryptographic hash function used in a cryptographic scheme is
formulated as a random variable uniformly distributed over all possibility of the function,
called the random oracle. The main result of this paper is to show that, for any
secure signature scheme in the random oracle model, there exists a specific computable
function which can instantiate the random oracle while keeping the security originally
proved in the random oracle model. In modern cryptography the generic group model
is used also for a similar purpose to the random oracle model. We show that the same
results hold for the generic group model.
In the process of proving the results, we introduce the notion of effective security,
demonstrating the importance of this notion in modern cryptography.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Cryptography and Algorithmic Randomness
Technical Report
oai:researchspace.auckland.ac.nz:2292/36382012-02-02T23:23:15Zcom_2292_122col_2292_3508
Khoussainov, B
Shore, R.A
2009-04-16T23:18:13Z
2009-04-16T23:18:13Z
2000-03
CDMTCS Research Reports CDMTCS-129 (2000)
1178-3540
http://hdl.handle.net/2292/3638
[no abstract available]
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Solutions of the Goncharov-Millar and Degree Spectra Problems in The Theory of Computable Models
Technical Report
oai:researchspace.auckland.ac.nz:2292/37282012-02-02T23:23:19Zcom_2292_122col_2292_3508
Calude, E
Mills, B
Mills, L
2009-04-16T23:17:39Z
2009-04-16T23:17:39Z
2003-06
CDMTCS Research Reports CDMTCS-221 (2003)
1178-3540
http://hdl.handle.net/2292/3728
Studies of computational complementarity properties in finite state interactive
automata may shed light on the nature of both quantum and classical computation.
But, complementarity is difficult to test even for small-size automata. This paper
introduces the concept of an observation graph of an automaton which is used as
the main tool for the design of an algorithm which tests, in a uniform manner, two
types of complementarity properties. Implementations have been run on a standard
desktop computer examining all 5-state binary automata.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
A Uniform Method for Testing Computational Complementarity
Technical Report
oai:researchspace.auckland.ac.nz:2292/105682012-02-09T11:41:56Zcom_2292_122col_2292_3508
Nicolescu, R.
2012-01-16T03:19:45Z
2012-01-16T03:19:45Z
2011
CDMTCS Research Reports CDMTCS-415 (2011)
1178-3540
http://hdl.handle.net/2292/10568
Our group’s recent quest has been to use P systems to model parallel and
distributed algorithms. Several framework extensions are recalled or detailed, in
particular, modular composition with information hiding, complex symbols, generic
rules, reified cell IDs, asynchronous operational modes, asynchronous complexity.
We motivate our proposals via P system models of several well-known distributed
algorithms, such as leader election and distributed echo. As another type of application,
we mention a dynamic programming algorithm for stereo matching in
image processing. We suggest criteria to assess the merits of this modelling approach
and offer preliminary evaluations of our proposed additional ingredients,
which have been useful in refactoring existing systems and could be useful to the
larger P systems community.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Parallel and Distributed Algorithms in P Systems
Technical Report
oai:researchspace.auckland.ac.nz:2292/35922012-02-02T23:23:15Zcom_2292_122col_2292_3508
Calude, C.S
Calude, E
Stefanescu, C
2009-04-16T23:10:39Z
2009-04-16T23:10:39Z
1998-05
CDMTCS Research Reports CDMTCS-083 (1998)
1178-3540
http://hdl.handle.net/2292/3592
In this paper we extend (and study) two computational complementary principles from Moore to Mealy automata which are finite machines possessing better “quantum-like” features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett’s method, for example). Mathematica experiments confirmed this hypothesis.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Computational Complementarity for Mealy Automata
Technical Report
oai:researchspace.auckland.ac.nz:2292/35912012-02-02T23:23:14Zcom_2292_122col_2292_3508
Calude, C.S
Dinneen, Michael
2009-04-16T23:10:31Z
2009-04-16T23:10:31Z
1998-05
CDMTCS Research Reports CDMTCS-082 (1998)
1178-3540
http://hdl.handle.net/2292/3591
[no abstract available]
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
News from New Zealand / Group-Theoretic Methods for Designing Networks
Technical Report
oai:researchspace.auckland.ac.nz:2292/494812020-01-11T11:36:36Zcom_2292_122col_2292_3508
Wei, Z
Link, S
2020-01-10T01:36:46Z
2020-01-10T01:36:46Z
2019
CDMTCS Research Reports CDMTCS-531 (2019)
1178-3540
http://hdl.handle.net/2292/49481
Computing the functional dependencies that hold on a given data set is one
of the most important problems in data profiling. Our research advances state-
of-the-art in various ways. Utilizing new data structures and original techniques
for the dynamic computation of stripped partitions, we devise a new hybridization
strategy that outperforms the best algorithms in terms of efficiency, column-, and
row-scalability. This is demonstrated on real-world benchmark data. We show that
current outputs contain many redundant functional dependencies, but canonical
covers greatly reduce output sizes. Smaller representations of outputs are easier
to comprehend and use. We propose the number of redundant data values as a
natural measure to rank the output of discovery algorithms. Our ranking assesses
the relevance of functional dependencies for the given data set.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Discovery and Ranking of Functional Dependencies
Technical Report
oai:researchspace.auckland.ac.nz:2292/36542012-02-02T23:23:15Zcom_2292_122col_2292_3508
Calude, C.S
Dinneen, Michael
Shu, C.-K
2009-04-16T23:14:50Z
2009-04-16T23:14:50Z
2000-11
CDMTCS Research Reports CDMTCS-146 (2000)
1178-3540
http://hdl.handle.net/2292/3654
A Chaitin Omega number is the halting probability of a universal Chaitin (selfdelimiting
Turing) machine. Every Omega number is both computably enumerable
(the limit of a computable, increasing, converging sequence of rationals) and
random (its binary expansion is an algorithmic random sequence). In particular,
every Omega number is strongly non-computable. The aim of this paper is to
describe a procedure, which combines Java and Perl programming and mathematical
proofs, for computing the exact values of the first 80 bits of a Chaitin Omega:
0.0000000000000000000010000001000000100000010000010000011100100111000101
0001010000. Full description of programs and proofs will be given elsewhere.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Computing 80 Initial Bits of A Chaitin Omega Number
Technical Report
oai:researchspace.auckland.ac.nz:2292/238912016-04-22T12:34:02Zcom_2292_122col_2292_3508
Abbott, AA
Calude, CS
Svozil, K
2015-01-05T00:14:04Z
2015-01-05T00:14:04Z
2014
CDMTCS Research Reports CDMTCS-458 (2014)
1178-3540
http://hdl.handle.net/2292/23891
We develop a general, non-probabilistic model of prediction which is suitable for assessing the
(un)predictability of individual physical events. We use this model to provide, for the first time, a rigorous
proof of the unpredictability of a class of individual quantum measurement outcomes, a well-known
quantum attribute postulated or claimed for a long time.
We prove that quantum indeterminism—formally modelled as value indefiniteness—-is incompatible
with the supposition of predictability: value indefinite observables are unpredictable. The proof makes
essential use of a strengthened form of the Kochen-Specker theorem proven previously to identify value
indefinite observables. As a result, quantum unpredictability, like the Kochen-Specker theorem, relies on
three assumptions: compatibility with quantum mechanical predictions, non-contextuality, and the value
definiteness of observables corresponding to the preparation basis of a quantum state.
Finally, quantum unpredictability is used to prove that quantum randomness is "maximally incomputable"
and to discuss a real model of hypercomputation whose computational power has yet to be determined. The
paper ends with a further open problem.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
On the Unpredictability of Individual Quantum Measurement Outcomes
Technical Report
oai:researchspace.auckland.ac.nz:2292/580062022-01-19T01:39:29Zcom_2292_122col_2292_3508
Agüero Trejo, JM
Calude, CS
2022-01-14T03:42:09Z
2022-01-14T03:42:09Z
2020
CDMTCS Research Reports CDMTCS-543 (2020)
1178-3540
https://hdl.handle.net/2292/58006
In this paper we propose a new ternary QRNG based on measuring located value indefinite observables with probabilities 1/4, 1/2, 1/4 and prove
that every sequence generated is maximally unpredictable, 3-bi-immune (a
stronger form of bi-immunity), and its prefixes are Borel normal. The ternary
quantum random digits produced by the QRNG are algorithmically transformed into quantum random bits using an alphabetic morphism which preserves all the above properties.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
A New Quantum Random Number Generator Certified by Value Indefiniteness
Technical Report
oai:researchspace.auckland.ac.nz:2292/238872016-04-22T12:34:48Zcom_2292_122col_2292_3508
Gavruskin, A
Khoussainov, B
Stephan, F
2015-01-05T00:14:03Z
2015-01-05T00:14:03Z
2014
CDMTCS Research Reports CDMTCS-456 (2014)
1178-3540
http://hdl.handle.net/2292/23887
In this paper we investigate the dependence of recursively enumerable
structures on the equality relation which is fixed to a specific
r.e. equivalence relation. We compare r.e. equivalence relations on the
natural numbers with respect to the amount of structures they permit
to represent from a given class of structures such as algebras, permutations
and linear orders. In particular, we show that for various types
of structures represented, there are minimal and maximal elements.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Reducibilities Among Equivalence Relations Induced by Recursively Enumerable Structures
Technical Report
oai:researchspace.auckland.ac.nz:2292/494902020-11-24T07:44:19Zcom_2292_122col_2292_3508
Liu, K
Dinneen, Michael
2020-01-10T02:29:23Z
2019-06
1178-3540
http://hdl.handle.net/2292/49490
This paper describes a new approach for finding an approximate Euclidean shortest path with additional constraints, which we call a multi-criterion shortest path, between two given points that avoids vertical obstacles in a three-dimensional space. Currently, there does not exist any polynomial-time algorithm that solves this problem exactly, even without additional constraints. Furthermore, existing approximation algorithms mostly focus on reducing the running time at the expense of the accuracy. Here, we aim at increasing the accuracy of an approximate shortest path. To this end, our new algorithm is based on geometric principles to determine all obstacle segments and partial obstacle segments that are visible to each other. Using this information, we employ Mixed Integer Linear Programming to compute an approximate shortest path between two given points. We test our algorithm on a number of test cases and find that our method returns approximate shortest paths that are shorter than those returned by other currently available algorithms. Moreover, our method is more flexible since it allows users to define additional constraints or criteria in exploring different types of optimal paths.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
Copyright: The author
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Solving the Bounded-Depth Steiner Tree Problem using an Adiabatic Quantum Computer
Report
oai:researchspace.auckland.ac.nz:2292/374922018-07-21T12:31:10Zcom_2292_122col_2292_3508
Calude, CS
Staiger, L
2018-07-18T04:42:50Z
2018-07-18T04:42:50Z
2017
CDMTCS Research Reports CDMTCS-505 (2017)
1178-3540
http://hdl.handle.net/2292/37492
A disjunctive sequence is an infinite sequence in which every finite string appears as a substring. An absolutely disjunctive number (or lexicon) is a real whose expansion with respect to every base is disjunctive. In this note we give a simple construction of absolutely disjunctive Liouville numbers (reals which can be “quite closely” approximated by sequences of rationals).
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
A simple construction of absolutely disjunctive Liouville numbers
Technical Report
oai:researchspace.auckland.ac.nz:2292/37512012-02-02T23:23:18Zcom_2292_122col_2292_3508
Schultes, D
2009-04-16T23:12:41Z
2009-04-16T23:12:41Z
2004-07
CDMTCS Research Reports CDMTCS-244 (2004)
1178-3540
http://hdl.handle.net/2292/3751
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Rainbow Sort:Sorting at the Speed of Light
Technical Report
oai:researchspace.auckland.ac.nz:2292/37242012-02-02T23:23:18Zcom_2292_122col_2292_3508
Calude, C.S
Calude, E
Dinneen, Michael
2009-04-16T23:13:53Z
2009-04-16T23:13:53Z
2003-05
CDMTCS Research Reports CDMTCS-217 (2003)
1178-3540
http://hdl.handle.net/2292/3724
For almost 350 years it was known that 1729 is the smallest integer which
can be expressed as the sum of two positive cubes in two different ways. Motivated
by a famous story involving Hardy and Ramanujan, a class of numbers called Taxicab
Numbers has been defined: Taxicab(k, j, n) is the smallest number which can
be expressed as the sum of j kth powers in n different ways. So, Taxicab(3, 2, 2) =
1729; Taxicab(4, 2, 2) = 635318657. Computing Taxicab Numbers is challenging and
interesting, both from mathematical and programming points of view.
The exact value of Taxicab(6) = Taxicab(3, 2, 6) is not known; however, recent
results announced by Rathbun [R2002] show that Taxicab(6) is in the interval
[1¹⁸, 24153319581254312065344]. In this note we show that with probability greater
than 99%, Taxicab(6) = 24153319581254312065344.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
What is the Value of Taxicab(6)?
Technical Report
oai:researchspace.auckland.ac.nz:2292/278562016-04-22T14:23:42Zcom_2292_122col_2292_3508
2016-01-04T21:55:58Z
2016-01-04T21:55:58Z
2015
CDMTCS Research Reports CDMTCS-487 (2015)
1178-3540
http://hdl.handle.net/2292/27856
We present a new variant of how catalytic P systems can simulate register machines, thus reducing again the number of rules needed for simulating register machines. Moreover, we show that only 20 rules are needed to generate a non-semilinear set of natural numbers by a catalytic P system with two catalysts. Finally, we establish improved versions of universal catalytic P systems.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
Proceedings of the Workshop on Membrane Computing 2015 (WMC2015)
Technical Report
oai:researchspace.auckland.ac.nz:2292/35822012-02-02T23:23:18Zcom_2292_122col_2292_3508
Paun, G
2009-04-16T23:16:33Z
2009-04-16T23:16:33Z
1997-12
CDMTCS Research Reports CDMTCS-073 (1997)
1178-3540
http://hdl.handle.net/2292/3582
We deal here with the computational capacity of DNA when
splicing it, by means of restriction enzymes and ligases. We introduce a
new distributed structure of a computing system (we call it two-level H
system), with each component working by splicing (according to internal
splicing rules) and communicating, also by splicing, according to external
splicing rules. This architecture is proven to be computationally universal,
systems with three components characterize the recursively enumerable
languages. The possibility of designing universal DNA computers based
on splicing is inferred on this basis.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Two-Level Distributed H Systems
Technical Report
oai:researchspace.auckland.ac.nz:2292/36432012-02-02T23:23:18Zcom_2292_122col_2292_3508
Calude, C.S
Dinneen, M.J
2009-04-16T23:13:27Z
2009-04-16T23:13:27Z
2000-05
CDMTCS Research Reports CDMTCS-134 (2000)
1178-3540
http://hdl.handle.net/2292/3643
These are the abstracts of talks to be given at the One-Day Workshop Discrete Mathematics and
Theoretical Computer Science Day to be held at the University Auckland on 26 May 2000 to mark the
5th anniversary of the Center for Discrete Mathematics and Theoretical Computer Science.
The Conference Committee for the workshop consisted of the following people: Douglas S. Bridges,
Canterbury, Cristian S. Calude, Auckland, Michael J. Dinneen, Auckland, John Hosking, Auckland,
Gaven Martin, Auckland, Alan Williamson, Auckland.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
The 5th Anniversary Workshop on Discrete Mathematics and Theoretical Computer Science
Technical Report
oai:researchspace.auckland.ac.nz:2292/198202013-01-07T11:31:57Zcom_2292_122col_2292_3508
ElGindy, H.
Nicolescu, R.
Wu, H
2013-01-06T23:09:24Z
2013-01-06T23:09:24Z
2012
CDMTCS Research Reports CDMTCS-431 (2012)
1178-3540
http://hdl.handle.net/2292/19820
We present two new synchronous distributed message-based depth-first search
(DFS) based algorithms, Algorithms C and D, to compute a maximum cardinality
set of edge-disjoint paths, between a source node and a target node in a digraph.
We compare these new algorithms with our previous implementation of the classical algorithm, Algorithm A, and our previous improvement, Algorithm B [10].
Empirical results show that, on a set of random digraphs, our algorithms are faster
than the classical Algorithm A, by a factor around 40%. All these improved algorithms have been inspired and guided by a P system modelling exercise, but are
suitable for any distributed implementation. To achieve the maximum theoretical
performance, our P systems specfication uses high-level generic rules applied in
matrix grammar mode.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Fast Distributed DFS Solutions for Edge-disjoint Paths in Digraphs
Technical Report
oai:researchspace.auckland.ac.nz:2292/37532012-02-02T23:23:13Zcom_2292_122col_2292_3508
Calude, C.S
Paun, G
2009-04-16T23:11:33Z
2009-04-16T23:11:33Z
2004-08
CDMTCS Research Reports CDMTCS-246 (2004)
1178-3540
http://hdl.handle.net/2292/3753
This is the text added to the Russian edition of our book Computing with
Cells and Atoms (Taylor & Francis Publishers, London, 2001) to be published
by Pushchino Publishing House. The translation was done by Professor Victor
Vladimirovich Ivanov and Professor Robert Polozov.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Computing with Cells and Atoms: After Five Years
Technical Report
oai:researchspace.auckland.ac.nz:2292/36632012-02-02T23:23:18Zcom_2292_122col_2292_3508
Donath, N
Svozil, K
2009-04-16T23:10:51Z
2009-04-16T23:10:51Z
2001-05
CDMTCS Research Reports CDMTCS-155 (2001)
1178-3540
http://hdl.handle.net/2292/3663
We consider the problem to single out a particular state among 2n orthogonal pure states. As it turns out, in general the optimal strategy is not to measure the particles separately, but to consider joint properties of the n-particle system. The required number of propositions is n. There exist 2n! equivalent operational procedures to do so. We enumerate some configurations for three particles, in particular the Greenberger-Horne-Zeilinger (GHZ) and W-states, which are specific cases of a unitary transformation. For the GHZ-case, an explicit physical meaning of the projection operators is discussed.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Finding a State in a Haystack
Technical Report
oai:researchspace.auckland.ac.nz:2292/35722012-02-02T23:23:13Zcom_2292_122col_2292_3508
Calude, C.S
Priese, L
Staiger, L
2009-04-16T23:11:42Z
2009-04-16T23:11:42Z
1997-10
CDMTCS Research Reports CDMTCS-063 (1997)
1178-3540
http://hdl.handle.net/2292/3572
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.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Disjunctive Sequences: An Overview
Technical Report
oai:researchspace.auckland.ac.nz:2292/198132013-01-07T11:31:58Zcom_2292_122col_2292_3508
Dinneen, M.J.
Wei, K
2013-01-06T23:09:23Z
2013-01-06T23:09:23Z
2012
CDMTCS Research Reports CDMTCS-424 (2012)
1178-3540
http://hdl.handle.net/2292/19813
A memetic algorithm is an evolutionary algorithm augmented with a local
search. This paper defines the (1+1) self-adjusting memetic algorithm with a dynamic mutation probability, and proposes a random permutation local search to
compare with a traditional random complete local search. Our time complexity
analysis proves that these two local searches can outperform each other on different functions. Also memetic algorithms with dynamic mutation probabilities can
outperform memetic algorithms with static mutation probabilities, and vice versa.
The success of our experimental results on the Maximum Clique Problem shows
the benefit of the self-adjusting strategy combined with the random permutation
local search. Also focusing on the Maximum Clique Problem, we propose another
time complexity metric (expected time to escape a local optimal) and show how
it bounds the expected running time of finding a maximum clique. This metric
provides insight and shows some advantages of our approach of using a dynamic
mutation probability and a random permutation local search.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
On the Analysis of a (1+1) Self-Adjusting Memetic Algorithm
Technical Report
oai:researchspace.auckland.ac.nz:2292/38092012-02-02T23:23:18Zcom_2292_122col_2292_3508
Chong, C.T
Nies, A
Yu, L
2009-04-16T23:15:33Z
2009-04-16T23:15:33Z
2007-03
CDMTCS Research Reports CDMTCS-302 (2007)
1178-3540
http://hdl.handle.net/2292/3809
[no abstract available]
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Higher Randomness Notions and Their Lowness Properties
Technical Report
oai:researchspace.auckland.ac.nz:2292/105362012-02-09T11:41:40Zcom_2292_122col_2292_3508
Calude, E.
2012-01-16T03:19:42Z
2012-01-16T03:19:42Z
2010
CDMTCS Research Reports CDMTCS-383 (2010)
1178-3540
http://hdl.handle.net/2292/10536
Proving that a dynamical system is chaotic is a central problem in chaos
theory [11]. In this note we apply the computational method developed in [4,
2, 3] to show that Fermat’s last theorem is in the lowest complexity class CU,1.
Using this result we prove the existence of a two-dimensional Hamiltonian
system for which the proof that the system has a Smale horseshoe is in the
class CU,1, i.e. it is not too complex.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Fermat's Last Theorem and Chaoticity
Technical Report
oai:researchspace.auckland.ac.nz:2292/35232012-02-02T23:23:18Zcom_2292_122col_2292_3508
Calude, C
2009-04-16T23:13:11Z
2009-04-16T23:13:11Z
1996-05
CDMTCS Research Reports CDMTCS-014 (1996)
1178-3540
http://hdl.handle.net/2292/3523
This note collects some open problems in AIT which have been discussed during the Summer
School \Chaitin Complexity and Applications". Each problem comes with the name(s) of the person(
s) who suggested it, and more details about the listed open problems can be found directly by contacting
the correspondent author.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Algorithmic Information Theory: Open Problems
Technical Report
oai:researchspace.auckland.ac.nz:2292/38072012-02-02T23:23:18Zcom_2292_122col_2292_3508
Hay, N.J
2009-04-16T23:15:12Z
2009-04-16T23:15:12Z
2007-02
CDMTCS Research Reports CDMTCS-300 (2007)
1178-3540
http://hdl.handle.net/2292/3807
Universal semimeasures [Hut05][LV97], a type of function derived from probability
and computability theory, describe extremely powerful sequence predictors. They
outperform all other predictors but for a penalty no more than the predictor’s complexity.
They learn to predict any computable sequence with error no more than
the sequence’s complexity. Universal semimeasures work by modelling the sequence
as generated by an unknown program running on a universal computer. Although
these predictors are uncomputable, and so cannot be implemented in practice, they
serve to describe an ideal: an existence proof for systems that predict better than
humans.
We review the mathematics behind universal semimeasures and discuss some of its
implications. Our approach differs from previous ones in several respects. We show
semimeasures correspond to probability measures over the set of finite and infinite
sequences, establishing a rigorous footing. We demonstrate the existence of universal
semimeasures using a novel proof of the equivalence between enumerable semimeasures
and processes. We take into account the possibility of sequence termination
leading to a stronger definition of universality. To make explicit hidden constants we
define a novel complexity measure, simulation complexity, which generalises monotone
complexity. Finally, we emphasise the use of logarithmic scoring rules [Ber79]
to measure error in prediction.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Universal Semimeasures: An Introduction
Technical Report
oai:researchspace.auckland.ac.nz:2292/36612012-02-02T23:23:14Zcom_2292_122col_2292_3508
Gunther, Ulrich
2009-04-16T23:13:59Z
2009-04-16T23:13:59Z
2001-04
CDMTCS Research Reports CDMTCS-153 (2001)
1178-3540
http://hdl.handle.net/2292/3661
A classic area of application for variable-length codes is data compression. This paper looks at a class of variable-length codes, the T-codes, that have been noted for their self-synchronisation properties. While the coding efficiency of T-codes is less than or equal to that of Huffman codes, no simple algorithm for the construction of T-codes from a given set of source symbol probabilities has been developed so far. To date, the only approach to finding the most efficient T-code set for a given source seems to be an exhaustive search, which to date has been too complex to be of much practical value. This paper describes some shortcuts for this search and presents recent improvements that yield a much lower computational complexity.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Matching T-Codes to a Source
Technical Report
oai:researchspace.auckland.ac.nz:2292/375012018-07-21T12:31:19Zcom_2292_122col_2292_3508
Calude, CS
Calude, E
2018-07-18T04:42:53Z
2018-07-18T04:42:53Z
2017
CDMTCS Research Reports CDMTCS-514 (2017)
1178-3540
http://hdl.handle.net/2292/37501
We present an idiosyncratic view of the race for quantum computational supremacy. Google’s approach and IBM challenge are examined. An unexpected side-effect of the race is the significant progress in designing fast classical algorithms. Quantum supremacy, if achieved, won’t make classical computing obsolete.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.
The Road to Quantum Computational Supremacy
Technical Report
oai:researchspace.auckland.ac.nz:2292/35202012-02-02T23:23:19Zcom_2292_122col_2292_3508
Arslanov, A
2009-04-16T23:13:42Z
2009-04-16T23:13:42Z
1996-01
CDMTCS Research Reports CDMTCS-011 (1996)
1178-3540
http://hdl.handle.net/2292/3520
We study here the degree-theoretic structure of set-theoretical splittings of recursively enumerable
(r.e.) sets into differences of r.e. sets. As a corollary we deduce that the ordering of wtt-degrees
of unsolvability of differences of r.e. sets is not a distributive semilattice and is not elementarily
equivalent to the ordering of r.e. wtt-degrees of unsolvability.
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Difference Splittings of Recursively Enumerable Sets
Technical Report
mods///col_2292_3508/100