2020-09-22T05:33:00Zhttps://researchspace.auckland.ac.nz/dspace-oai/requestoai:researchspace.auckland.ac.nz:2292/35092012-02-02T23:23:13Zcom_2292_122col_2292_3508
An initial-algebra approach to directed acyclic graphs
Gibbons, Jenny
The initial-algebra approach to modelling datatypes consists of giving constructors
for building larger objects of that type from smaller ones, and laws identifying different ways
of constructing the same object. The recursive decomposition of objects of the datatype leads
directly to a recursive pattern of computation on those objects, which is very helpful for both
functional and parallel programming.
We show how to model a particular kind of directed acyclic graph using this initial-algebra
approach.
2009-04-14T23:08:28Z
2009-04-14T23:08:28Z
2009-04-14T23:08:28Z
1995-04
Technical Report
CDMTCS Research Report Series CDMTCS-001 (1995)
http://hdl.handle.net/2292/3509
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36652012-02-02T23:23:17Zcom_2292_122col_2292_3508
A Conference Submission Web Server
Lee, S.Y.P
Dinneen, Michael
We present a conference submission web server that supports conference
organizers to manage the process of receiving and evaluating conference papers.
The main features of our conference submission web server include effective
operations and transactions, simple and flexible user interfaces, platform
independence and reusability. The system models a conference organized by the
Center for Discrete Mathematics and Theoretical Computer Science
(Auckland, New Zealand). It is designed and implemented as a standalone
application. It can be, however easily plugged into an existing conference web
site.
2009-04-16T23:09:45Z
2009-04-16T23:09:45Z
2009-04-16T23:09:45Z
2001-06
Technical Report
CDMTCS Research Reports CDMTCS-157 (2001)
1178-3540
http://hdl.handle.net/2292/3665
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37472012-02-02T23:23:13Zcom_2292_122col_2292_3508
Automata Recognizing No Words: A Statistical Approach
Calude, C.S
Campeanu, C
Dumitrescu, M
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.
2009-04-16T23:09:48Z
2009-04-16T23:09:48Z
2009-04-16T23:09:48Z
2004-05
Technical Report
CDMTCS Research Reports CDMTCS-240 (2004)
1178-3540
http://hdl.handle.net/2292/3747
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37272012-02-02T23:23:17Zcom_2292_122col_2292_3508
A Fast Natural Algorithm for Searching
Arulanandham, J.J
Calude, C.S
Dinneen, Michael
In this note we present two natural algorithms—one for sorting, and another
for searching a sorted list of items. Both algorithms work in O(√N) time, N being
the size of the list. A combination of these algorithms can search an unsorted list
in O(√N) time, an impossibility for classical algorithms. The same complexity is
achieved by Grover’s quantum search algorithm; in contrast to Grover’s algorithm
which is probabilistic, our method is guaranteed correct. Two applications will
conclude this note.
2009-04-16T23:09:50Z
2009-04-16T23:09:50Z
2009-04-16T23:09:50Z
2003-06
Technical Report
CDMTCS Research Reports CDMTCS-220 (2003)
1178-3540
http://hdl.handle.net/2292/3727
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35732012-02-02T23:23:16Zcom_2292_122col_2292_3508
Surjective Functions on Computably Growing Cantor Sets
Hertling, P
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.
2009-04-16T23:09:52Z
2009-04-16T23:09:52Z
2009-04-16T23:09:52Z
1997-10
Technical Report
CDMTCS Research Reports CDMTCS-064 (1997)
1178-3540
http://hdl.handle.net/2292/3573
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37682012-02-02T23:23:13Zcom_2292_122col_2292_3508
What is the Value of Taxicab(6)? An Update
Calude, C.S
Calude, E
Dinneen, Michael
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%.
2009-04-16T23:09:54Z
2009-04-16T23:09:54Z
2009-04-16T23:09:54Z
2005-04
Technical Report
CDMTCS Research Reports CDMTCS-261 (2005)
1178-3540
http://hdl.handle.net/2292/3768
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36272012-02-02T23:23:17Zcom_2292_122col_2292_3508
The Minor-Order Obstructions for The Graphs of Vertex Cover Six
Dinneen, Michael
Xiong, Liu
We provide for the first time a complete list of forbidden minors (obstructions)
for the family of graphs with vertex cover 6. This paper shows how to
limit both the search space of graphs and improve the efficiency of an obstruction
checking algorithm when restricted to k–Vertex Cover graph families.
In particular, our upper bounds 2k + 1 (2k + 2) on the maximum number of
vertices for connected (disconnected) obstructions are shown to be sharp for all
k > 0.
2009-04-16T23:09:55Z
2009-04-16T23:09:55Z
2009-04-16T23:09:55Z
2000-01
Technical Report
CDMTCS Research Reports CDMTCS-118 (2000)
1178-3540
http://hdl.handle.net/2292/3627
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36952012-02-02T23:23:13Zcom_2292_122col_2292_3508
Another Example of Higher Order Randomness
Becher, V
Chaitin, G.J
We consider the notion of randomness relative to an oracle: a real number is
random in A if and only if its initial segments are algorithmically incompressible
in a self-delimiting universal machine equipped with an oracle A. We prove that
the probability that a program for infinite computations outputs a cofinite set is
random in the second jump of the halting problem.
2009-04-16T23:09:57Z
2009-04-16T23:09:57Z
2009-04-16T23:09:57Z
2002-05
Technical Report
CDMTCS Research Reports CDMTCS-187 (2002)
1178-3540
http://hdl.handle.net/2292/3695
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36242012-02-02T23:23:13Zcom_2292_122col_2292_3508
Computable $p$-adic Numbers
Kapoulas, G
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.
2009-04-16T23:09:59Z
2009-04-16T23:09:59Z
2009-04-16T23:09:59Z
1999-11
Technical Report
CDMTCS Research Reports CDMTCS-115 (1999)
1178-3540
http://hdl.handle.net/2292/3624
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37712012-02-02T23:23:15Zcom_2292_122col_2292_3508
Infinite Iterated Function Systems in Cantor Space and the Hausdorff Measure of omega-power Languages
Staiger, L
We use means of formal language theory to estimate the Hausdorff measure
of sets of a certain shape in Cantor space. These sets are closely related
to infinite iterated function systems in fractal geometry.
Our results are used to provide a series of simple examples for the noncoincidence
of limit sets and attractors for infinite iterated function systems.
2009-04-16T23:10:00Z
2009-04-16T23:10:00Z
2009-04-16T23:10:00Z
2005-04
Technical Report
CDMTCS Research Reports CDMTCS-264 (2005)
1178-3540
http://hdl.handle.net/2292/3771
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37742012-02-02T23:23:13Zcom_2292_122col_2292_3508
A Comparison of Practical Information Measures
Titchener, M.R
Speidel, U
Yang, J
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.
2009-04-16T23:10:02Z
2009-04-16T23:10:02Z
2009-04-16T23:10:02Z
2005-05
Technical Report
CDMTCS Research Reports CDMTCS-267 (2005)
1178-3540
http://hdl.handle.net/2292/3774
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37962012-02-02T23:23:18Zcom_2292_122col_2292_3508
Longest Alternating Subsequences in Pattern-Restricted Permutations
Firror, G
Mansour, T
Wilson, Mark
Inspired by the results of Stanley and Widom concerning the limiting distribution of the lengths of longest alternating subsequences in random permutations, and the results of Deutsch, Hildebrand and Wilf on the limiting distribution of the longest increasing subsequence for pattern-restricted permutations, we find the limiting distribution of the longest alternating subsequence for pattern-restricted permutations in which the pattern is any one of the six patterns of length three. Our methodology uses recurrences, generating functions, and complex analysis, and also yields more detailed information. Several ideas for future research are listed.
2009-04-16T23:10:04Z
2009-04-16T23:10:04Z
2009-04-16T23:10:04Z
2006-10
Technical Report
CDMTCS Research Reports CDMTCS-289 (2006)
1178-3540
http://hdl.handle.net/2292/3796
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37932012-02-02T23:23:16Zcom_2292_122col_2292_3508
T-Complexity and T-Information Theory--an Executive Summary, 2nd revised version
Speidel, U
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.
2009-04-16T23:10:05Z
2009-04-16T23:10:05Z
2009-04-16T23:10:05Z
2006-10
Technical Report
CDMTCS Research Reports CDMTCS-286 (2006)
1178-3540
http://hdl.handle.net/2292/3793
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35742012-02-02T23:23:14Zcom_2292_122col_2292_3508
Embedding Cellular Automata into Reversible Ones
Hertling, P
Toffoli showed that every cellular automaton of an arbitrary dimension d can be embedded into a
reversible cellular automaton of dimension d+1. He asked “whether an arbitrary cellular automaton
can be embedded in a reversible one having the same number of dimensions” and conjectured that
this is not possible. We show that his conjecture is true. Even if one imposes only a weak, natural
condition on embeddings, no cellular automaton which possesses a Garden of Eden configuration
can be embedded into a reversible cellular automaton of the same dimension.
2009-04-16T23:10:07Z
2009-04-16T23:10:07Z
2009-04-16T23:10:07Z
1997-10
Technical Report
CDMTCS Research Reports CDMTCS-065 (1997)
1178-3540
http://hdl.handle.net/2292/3574
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38672012-02-02T23:23:14Zcom_2292_122col_2292_3508
On the Brightness of the Thomson lamp. A Prolegomenon to Quantum Recursion Theory
Svozil, K
Some quantum cryptographic protocols can be implemented with specially prepared
chocolate balls, others protected by value indefiniteness cannot. Similarities and differences
of cryptography with quanta and chocolate are discussed. Motivated by these considerations
it is proposed to certify quantum random number generators and quantum cryptographic
protocols by value indefiniteness. This feature, which derives itself from Belland
Kochen-Specker type arguments, is only present in systems with three or more mutually
exclusive outcomes.
2009-04-16T23:10:09Z
2009-04-16T23:10:09Z
2009-04-16T23:10:09Z
2009-04
Technical Report
CDMTCS Research Reports CDMTCS-360 (2009)
1178-3540
http://hdl.handle.net/2292/3867
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37922012-02-02T23:23:15Zcom_2292_122col_2292_3508
De-Quantising the Solution of Deutsch's Prolem
Calude, C.S
Probably the simplest and most frequently used way to illustrate the power of quantum
computing is to solve the so-called Deutsch’s problem. Consider a Boolean function f :
{0,1}→{0,1} and suppose that we have a (classical) black box to compute it. The problem
asks whether f is constant (that is, f (0) = f (1)) or balanced ( f (0) ≠ f (1)). Classically, to
solve the problem seems to require the computation of f (0) and f (1), and then the comparison
of results. Is it possible to solve the problem with only one query on f ? In a famous paper
published in 1985, Deutsch posed the problem and obtained a “quantum” partial affirmative
answer. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello,
and Mosca. Here we will show that the quantum solution can be de-quantised to a
deterministic simpler solution which is as efficient as the quantum one. The use of “superposition”,
a key ingredient of quantum algorithm, is—in this specific case—classically available.
2009-04-16T23:10:10Z
2009-04-16T23:10:10Z
2009-04-16T23:10:10Z
2006-08
Technical Report
CDMTCS Research Reports CDMTCS-285 (2006)
1178-3540
http://hdl.handle.net/2292/3792
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36932012-02-02T23:23:17Zcom_2292_122col_2292_3508
Some Thoughts On Automatic Structures
Khoussainov, B
Rubin, S
Our aim in writing this paper is twofold. On the one hand, we present the theory
of automatic structures from the points of view of model theory, algebra, complexity
theory, and automata theory. On the other hand, we survey basic results and present
possible directions for future research in the area.
--from Introduction
2009-04-16T23:10:12Z
2009-04-16T23:10:12Z
2009-04-16T23:10:12Z
2002-05
Technical Report
CDMTCS Research Reports CDMTCS-185 (2002)
1178-3540
http://hdl.handle.net/2292/3693
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37702012-02-02T23:23:13Zcom_2292_122col_2292_3508
Twenty Combinatorial Examples of Asymptotics Derived From Multivariate Generating Functions
Pemantle, R
Wilson, Mark
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.
2009-04-16T23:10:13Z
2009-04-16T23:10:13Z
2009-04-16T23:10:13Z
2005-04
Technical Report
CDMTCS Research Reports CDMTCS-263 (2005)
1178-3540
http://hdl.handle.net/2292/3770
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36672012-02-02T23:23:13Zcom_2292_122col_2292_3508
A Constructive Theory of Point-Set Nearness
Bridges, D.S
Vita, L.S
An axiomatic constructive development of the theory of nearness and apartness
of a point and a set is introduced as a setting for topology.
2009-04-16T23:10:15Z
2009-04-16T23:10:15Z
2009-04-16T23:10:15Z
2001-08
Technical Report
CDMTCS Research Reports CDMTCS-159 (2001)
1178-3540
http://hdl.handle.net/2292/3667
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37492012-02-02T23:23:17Zcom_2292_122col_2292_3508
Fast Generation of Fibonacci Permutations
Juarna, A
Vajnovszki, V
[no abstract available]
2009-04-16T23:10:16Z
2009-04-16T23:10:16Z
2009-04-16T23:10:16Z
2004-07
Technical Report
CDMTCS Research Reports CDMTCS-242 (2004)
1178-3540
http://hdl.handle.net/2292/3749
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35932012-02-02T23:23:18Zcom_2292_122col_2292_3508
Breaking the Turing Barrier
Calude, C.S
Dinneen, Michael
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.
2009-04-16T23:10:18Z
2009-04-16T23:10:18Z
2009-04-16T23:10:18Z
1998-05
Technical Report
CDMTCS Research Reports CDMTCS-084 (1998)
1178-3540
http://hdl.handle.net/2292/3593
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36002012-02-02T23:23:17Zcom_2292_122col_2292_3508
Abstracts of the 2nd Japan - New Zealand Workshop on Logic in Computer Science
Dinneen, M.J
[no abstract available]
2009-04-16T23:10:20Z
2009-04-16T23:10:20Z
2009-04-16T23:10:20Z
1998-10
Technical Report
CDMTCS Research Reports CDMTCS-091 (1998)
1178-3540
http://hdl.handle.net/2292/3600
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37912012-02-02T23:23:17Zcom_2292_122col_2292_3508
Most Short Programs Halt Quickly or Never Halt
Calude, C.S
Stay, M.A
The aim of this paper is to provide a probabilistic, but non-quantum, analysis
of the Halting Problem. Our approach is to have the probability space extend over
both space and time and to consider the probability that a random N-bit program
has halted by a random time. We postulate an a priori computable probability
distribution on all possible runtimes and we prove that given an integer k > 0, we
can effectively compute a time bound T such that the probability that an N-bit
program will eventually halt given that it has not halted by T is smaller than 2−k.
We also show that the set of halting programs (which is computably enumerable,
but not computable) can be written as a disjoint union of a computable set and a
set of effectively vanishing probability.
Finally, we show that “long” runtimes are effectively rare. More formally, the
set of times at which an N-bit program can stop after the time 2N+constant has
effectively zero density.
2009-04-16T23:10:21Z
2009-04-16T23:10:21Z
2009-04-16T23:10:21Z
2006-08
Technical Report
CDMTCS Research Reports CDMTCS-284 (2006)
1178-3540
http://hdl.handle.net/2292/3791
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37722012-02-02T23:23:17Zcom_2292_122col_2292_3508
Very Simple Chaitin Machines for Concrete AIT
Stay, M
In 1975, Chaitin introduced his celebrated Omega number, the
halting probability of a universal Chaitin machine, a universal Turing machine
with a prefix-free domain. The Omega number’s bits are algorithmically
random—there is no reason the bits should be the way they are, if we define
“reason” to be a computable explanation smaller than the data itself. Since
that time, only two explicit universal Chaitin machines have been proposed,
both by Chaitin himself.
Concrete algorithmic information theory involves the study of particular
universal Turing machines, about which one can state theorems with specific
numerical bounds, rather than include terms like O(1). We present several
new tiny Chaitin machines (those with a prefix-free domain) suitable for the
study of concrete algorithmic information theory. One of the machines, which
we call Keraia, is a binary encoding of lambda calculus based on a curried
lambda operator. Source code is included in the appendices.
We also give an algorithm for restricting the domain of blank-endmarker
machines to a prefix-free domain over an alphabet that does not include the
endmarker; this allows one to take many universal Turing machines and construct
universal Chaitin machines from them.
2009-04-16T23:10:23Z
2009-04-16T23:10:23Z
2009-04-16T23:10:23Z
2005-05
Technical Report
CDMTCS Research Reports CDMTCS-265 (2005)
1178-3540
http://hdl.handle.net/2292/3772
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36442012-02-02T23:23:16Zcom_2292_122col_2292_3508
Presentations of Computably Enumerable Reals
Downey, R.G
LaForte, G.L
We study the relationship between a computably enumerable real
and its presentations: ways of approximating the real by enumerating
a pre x-free set of binary strings.
2009-04-16T23:10:24Z
2009-04-16T23:10:24Z
2009-04-16T23:10:24Z
2000-05
Technical Report
CDMTCS Research Reports CDMTCS-135 (2000)
1178-3540
http://hdl.handle.net/2292/3644
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35212012-02-02T23:23:14Zcom_2292_122col_2292_3508
Quantum Electronic Devices Based on Metal-Dielectric Transition in Low-Dimensional Quantum Structures
Antoniou, I
Pavlov, B
Yafyasov, A
[no abstract available]
2009-04-16T23:10:25Z
2009-04-16T23:10:25Z
2009-04-16T23:10:25Z
1996-04
Technical Report
CDMTCS Research Reports CDMTCS-012 (1996)
1178-3540
http://hdl.handle.net/2292/3521
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36452012-02-02T23:23:15Zcom_2292_122col_2292_3508
Quantum Interfaces
Svozil, K
Rational agents acting as observers use “knowables” to construct a vision of the outside world.
Thereby, they are bound by the information exchanged with what they consider as objects. The
cartesian cut or, in modern terminology, the interface mediating this exchange, is again a construction.
It serves as a “scaffolding,” an intermediate construction capable of providing the necessary
conceptual means.
An attempt is made to formalize the interface, in particular the quantum interface and quantum
measurements, by a symbolic information exchange. A principle of conservation of information is
reviewed and a measure of information flux through the interface is proposed.
We cope with the question of why observers usually experience irreversibility in measurement
processes if the evolution is reversible, i.e., one-to-one. And why should there be any meaningful
concept of classical information if there is merely quantum information to begin with? We take the
position here that the concept of irreversible measurement is no deep principle but originates in the
practical inability to reconstruct a quantum state of the object.
Many issues raised apply also to the quantum’s natural double, virtual reality.
An experiment is proposed to test the conjecture that the self is transcendent.
2009-04-16T23:10:27Z
2009-04-16T23:10:27Z
2009-04-16T23:10:27Z
2000-05
Technical Report
CDMTCS Research Reports CDMTCS-136 (2000)
1178-3540
http://hdl.handle.net/2292/3645
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35222012-02-02T23:23:15Zcom_2292_122col_2292_3508
Kraft-Chaitin Inequality Revisited
Calude, C
Grozea, C
Kraft's inequality [9] is essential for the classical theory of noiseless coding [1, 8]. In algorithmic
information theory [5, 7, 2] one needs an extension of Kraft's condition from finite sets to (infinite)
recursively enumerable sets. This extension, known as Kraft-Chaitin Theorem, was obtained by
Chaitin in his seminal paper [4] (see also, [3, 2], [10]). The aim of this note is to offer a simpler proof
of Kraft-Chaitin Theorem based on a new construction of the prefix-free code.
2009-04-16T23:10:28Z
2009-04-16T23:10:28Z
2009-04-16T23:10:28Z
1996-04
Technical Report
CDMTCS Research Reports CDMTCS-013 (1996)
1178-3540
http://hdl.handle.net/2292/3522
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37952012-02-02T23:23:19Zcom_2292_122col_2292_3508
The Diameter of Random Cayley Digraphs of Given Degree
Lladser, M.E
Potocnik, P
Siran, J
Siagiova, J
Wilson, M.C
We consider random Cayley digraphs of order n with uniformly distributed
generating set of size k. Specifically, we are interested in the asymptotics of the
probability such a Cayley digraph has diameter two as n →∞ and k = f(n). We
find a sharp phase transition from 0 to 1 as the order of growth of f(n) increases
past √log n. In particular, if f(n) is asymptotically linear in n, the probability
converges exponentially fast to 1.
2009-04-16T23:10:30Z
2009-04-16T23:10:30Z
2009-04-16T23:10:30Z
2006-10
Technical Report
CDMTCS Research Reports CDMTCS-288 (2006)
1178-3540
http://hdl.handle.net/2292/3795
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35912012-02-02T23:23:14Zcom_2292_122col_2292_3508
News from New Zealand / Group-Theoretic Methods for Designing Networks
Calude, C.S
Dinneen, Michael
[no abstract available]
2009-04-16T23:10:31Z
2009-04-16T23:10:31Z
2009-04-16T23:10:31Z
1998-05
Technical Report
CDMTCS Research Reports CDMTCS-082 (1998)
1178-3540
http://hdl.handle.net/2292/3591
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37892012-02-02T23:23:14Zcom_2292_122col_2292_3508
Speculations on Biology, Information and Complexity
Chaitin, G.J
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.
2009-04-16T23:10:33Z
2009-04-16T23:10:33Z
2009-04-16T23:10:33Z
2006-07
Technical Report
CDMTCS Research Reports CDMTCS-282 (2006)
1178-3540
http://hdl.handle.net/2292/3789
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37732012-02-02T23:23:18Zcom_2292_122col_2292_3508
Network Event Detection with T-Entropy
Eimann, R
Speidel, U
Brownlee, N
Yang, J
This paper describes an entropy-based approach for the detection of network events.
This is achieved by first converting a stream of network packets into a string and then
computing its approximate average entropy rate using a computable complexity measure.
Changes in the average entropy rate are interpreted as events. The computational
complexity of the presented approach is nearly linear which makes this technique suitable
for online scenarios. We present the results of several measurements on actual
network data and show that it is indeed possible to associate actual network events
with changes in entropy.
2009-04-16T23:10:35Z
2009-04-16T23:10:35Z
2009-04-16T23:10:35Z
2005-05
Technical Report
CDMTCS Research Reports CDMTCS-266 (2005)
1178-3540
http://hdl.handle.net/2292/3773
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36422012-02-02T23:23:15Zcom_2292_122col_2292_3508
Computational Methods and New Results for Chessboard Problems
Kearse, M.D
Gibbons, P.B
We describe various computing techniques for tackling chessboard domination problems
and apply these to the determination of domination and irredundance numbers
for queens’ and kings’ graphs. In particular we show that γ(Q15) = γ(Q16) = 9 ,
confirm that γ(Q17) = γ(Q18) = 9, show that γ(Q19) = 10, show that i(Q18) = 10,
improve the bound for i(Q19) to 10 ≤ i(Q19) ≤ 11, show that ir(Qn) = γ(Qn) for
1 ≤ n ≤ 13, show that IR(Q9) = Γ(Q9) = 13 and that IR(Q10) = Γ(Q10) = 15, show
that γ(Q4k+1) = 2k +1 for 16 ≤ k ≤ 21, improve the bound for i(Q22) to i(Q22) ≤ 12,
and show that IR(K8) = 17, IR(K9) = 25, IR(K10) = 27, and IR(K11) = 36.
2009-04-16T23:10:36Z
2009-04-16T23:10:36Z
2009-04-16T23:10:36Z
2000-05
Technical Report
CDMTCS Research Reports CDMTCS-133 (2000)
1178-3540
http://hdl.handle.net/2292/3642
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36072012-02-02T23:23:16Zcom_2292_122col_2292_3508
Computing with Membranes: A Variant
Paun, G
We propose here a variant of the super-cell systems (also called, for
short, P systems), which looks less restrictive (more realistic) than the variants
investigated so far. In P systems as introduced in [7] (see a survey in [8]), the use
of objects evolution rules is regulated by a given priority relation; moreover, each
membrane has a label and one can send objects to precise membranes, identified
by their labels. We get rid of both there rather artificial (non-biochemical) features. Instead, we add to membranes and to objects an \electrical charge" and
the objects are passed through membranes according to their charge. We prove
that such systems are able to characterize the one-letter recursively enumerable
languages (equivalently, the recursively enumerable sets of natural numbers),
providing that an extra feature is considered: the membranes can be made
thicker or thinner (also dissolved, as in [7]) and the communication through
a membrane is possible only when its thickness is equal to 1. Several open
problems are formulated.
2009-04-16T23:10:38Z
2009-04-16T23:10:38Z
2009-04-16T23:10:38Z
1999-03
Technical Report
CDMTCS Research Reports CDMTCS-098 (1999)
1178-3540
http://hdl.handle.net/2292/3607
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35922012-02-02T23:23:15Zcom_2292_122col_2292_3508
Computational Complementarity for Mealy Automata
Calude, C.S
Calude, E
Stefanescu, C
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.
2009-04-16T23:10:39Z
2009-04-16T23:10:39Z
2009-04-16T23:10:39Z
1998-05
Technical Report
CDMTCS Research Reports CDMTCS-083 (1998)
1178-3540
http://hdl.handle.net/2292/3592
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35752012-02-02T23:23:17Zcom_2292_122col_2292_3508
Feedback for Relations
Cazanescu, V.E
In our previous papers [3,2] we have proved that there are nine types of finite relations
which are closed under a natural definition of feedback. In this note we prove that this
natural definition is the unique feedback which satisfies the axioms of a biflow over there
usual composition and sum.
2009-04-16T23:10:41Z
2009-04-16T23:10:41Z
2009-04-16T23:10:41Z
1997-11
Technical Report
CDMTCS Research Reports CDMTCS-066 (1997)
1178-3540
http://hdl.handle.net/2292/3575
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37882012-02-02T23:23:17Zcom_2292_122col_2292_3508
Is Incompleteness A Serious Problem
Chaitin, G.J
[no abstract available]
2009-04-16T23:10:42Z
2009-04-16T23:10:42Z
2009-04-16T23:10:42Z
2006-07
Technical Report
CDMTCS Research Reports CDMTCS-281 (2006)
1178-3540
http://hdl.handle.net/2292/3788
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35192012-02-02T23:23:18Zcom_2292_122col_2292_3508
Higman's Embedding Theorem. An Elementary Proof
Dediu, L
In 1961 G. Higman proved a remarkable theorem establishing a deep connection between the
logical notion of recursiveness and questions about finitely presented groups.
The basic aim of the present paper is to provide the reader with a rigorous and detailed proof
of Higman's Theorem. All the necessary preliminary material, including elements of group theory
and recursive functions theory, is systematically presented and with complete proofs. The aquainted
reader may skip the first sections and proceed immediately to the last.
2009-04-16T23:10:43Z
2009-04-16T23:10:43Z
2009-04-16T23:10:43Z
1995-10
Technical Report
CDMTCS Research Reports CDMTCS-010 (1995)
1178-3540
http://hdl.handle.net/2292/3519
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37442012-02-02T23:23:19Zcom_2292_122col_2292_3508
Finite Automata Encoding Geometric Figures
Juergensen, H
Staiger, L
Yamasaki, H
Finite automata are used for the encoding and compression of images. For
black-and-white images, for instance, using the quad-tree representation, the
black points correspond to ω-words defining the corresponding paths in the
tree that lead to them. If the ω-language consisting of the set of all these
words is accepted by a deterministic finite automaton then the image is said
to be encodable as a finite automaton. For grey-level images and colour images
similar representations by automata are in use.
In this paper we address the question of which images can be encoded as
finite automata with full infinite precision. In applications, of course, the image
would be given and rendered at some finite resolution – this amounts to
considering a set of finite prefixes of the ω-language – and the features in the
image would be approximations of the features in the infinite precision rendering.
We focus on the case of black-and-white images – geometrical figures, to
be precise – but treat this case in a d-dimensional setting, where d is any
positive integer. We show that among all polygons and convex polyhedra in
d-dimensional space exactly those with rational corner points are encodable
as finite automata.
In the course of proving this we show that the set of images encodable as
finite automata is closed under rational affine transformations.
Several properties of images encodable as finite automata are consequences
of this result. Finally we show that many simple geometric figures such as
circles and parabolas are not encodable as finite automata.
2009-04-16T23:10:45Z
2009-04-16T23:10:45Z
2009-04-16T23:10:45Z
2004-04
Technical Report
CDMTCS Research Reports CDMTCS-237 (2004)
1178-3540
http://hdl.handle.net/2292/3744
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38482012-02-02T23:23:14Zcom_2292_122col_2292_3508
Context-Aware Adaptation. A Case Study on Mathematical Notations
Müller, C
Kohlhase, M
In the last two decades, the World Wide Web has become the universal, and – for many users – main information source. Search engines can efficiently serve daily life
information needs due to the enormous redundancy of relevant resources on the web. For
educational – and even more so for scientific information needs, the web functions much
less efficiently: Scientific publishing is built on a culture of unique reference publications,
and moreover abounds with specialized structures, such as technical nomenclature, notational
conventions, references, tables, or graphs. Moreover, many of these structures are
peculiar to specialized communities determined by nationality, research group membership,
or adherence to a special school of thought. To keep the much-lamented “digital
divide" from becoming a “cultural divide", we have to make online material more accessible
and adaptable to individual users.
In this paper we attack this goal for the field of mathematics where knowledge is
abstract, highly structured, and extraordinarily interlinked. Modern, content-based representation
formats like OpenMath or content MathML allow us to capture, model,
relate, and represent mathematical knowledge objects and thus make them context-aware
and machine-adaptable to the respective user contexts. Building on previous work which
can make mathematical notations adaptable we employ user modeling techniques to make
them adaptive to relieve the reader of configuration tasks. We present a comprehensive
framework for adaptive notation management and evaluate it on an implementation
integrated in the e-learning platform panta rhei.
2009-04-16T23:10:46Z
2009-04-16T23:10:46Z
2009-04-16T23:10:46Z
2008-11
Technical Report
CDMTCS Research Reports CDMTCS-341 (2008)
1178-3540
http://hdl.handle.net/2292/3848
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37752012-02-02T23:23:16Zcom_2292_122col_2292_3508
Quantum Theory Looks at Time Travel
Greenberger, D.M
Svozil, K
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.
2009-04-16T23:10:48Z
2009-04-16T23:10:48Z
2009-04-16T23:10:48Z
2005-06
Technical Report
CDMTCS Research Reports CDMTCS-268 (2005)
1178-3540
http://hdl.handle.net/2292/3775
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36602012-02-02T23:23:14Zcom_2292_122col_2292_3508
Supplemental Abstracts for DMTCS01
Calude, C.S
Dinneen, Michael
Sburlan, S
These are the abstracts of the poster talks to be given at the 3rd International Conference Discrete Mathematics and Theoretical Computer Science, 2001, to be held at the ‘Ovidus’ University, Constanta, Romania, on July 2-6. 2001.
2009-04-16T23:10:49Z
2009-04-16T23:10:49Z
2009-04-16T23:10:49Z
2001-04
Technical Report
CDMTCS Research Reports CDMTCS-152 (2001)
1178-3540
http://hdl.handle.net/2292/3660
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36632012-02-02T23:23:18Zcom_2292_122col_2292_3508
Finding a State in a Haystack
Donath, N
Svozil, K
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.
2009-04-16T23:10:51Z
2009-04-16T23:10:51Z
2009-04-16T23:10:51Z
2001-05
Technical Report
CDMTCS Research Reports CDMTCS-155 (2001)
1178-3540
http://hdl.handle.net/2292/3663
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37192012-02-02T23:23:13Zcom_2292_122col_2292_3508
Complexity and Randomness
Terwijn, S.A
[no abstract available]
2009-04-16T23:10:52Z
2009-04-16T23:10:52Z
2009-04-16T23:10:52Z
2003-03
Technical Report
CDMTCS Research Reports CDMTCS-212 (2003)
1178-3540
http://hdl.handle.net/2292/3719
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36262012-02-02T23:23:16Zcom_2292_122col_2292_3508
A Glimpse into Natural Computing
Calude, C.S
Paun, G
Tataram, Monica
We consider as pertaining to Natural Computing (in some sense,
characterizing it) the following five domains: Neural Networks, Genetic Algorithms,
DNA Computing, Membrane Computing, and Quantum Computing.
The first two domains are well established, the last three are just now looking
for a place in the toolkit of practitioners. Here, we briefly introduce the last
three domains to the reader. The main point is that in all these areas one
aims at solving intractable (NP-complete) problems in polynomial (in many
cases, even linear) time. Taking into account that most significant practical
problems (optimization, scheduling, programming, combinatorial, etc.) are
intractable, it follows that the promises of Natural Computing should be
taken seriously.
2009-04-16T23:10:54Z
2009-04-16T23:10:54Z
2009-04-16T23:10:54Z
1999-12
Technical Report
CDMTCS Research Reports CDMTCS-117 (1999)
1178-3540
http://hdl.handle.net/2292/3626
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37762012-02-02T23:23:12Zcom_2292_122col_2292_3508
Characterization of Quantum Computable Decision Problems by State Discrimination
Svozil, K
One advantage of quantum algorithms over classical computation is the possibility to spread out, process, analyse
and extract information in multipartite configurations in coherent superpositions of classical states. This will be discussed
in terms of quantum state identification problems based on a proper partitioning of mutually orthogonal sets of states. The
question arises whether or not it is possible to encode equibalanced decision problems into quantum systems, so that a single
invocation of a filter used for state discrimination suffices to obtain the result.
2009-04-16T23:10:56Z
2009-04-16T23:10:56Z
2009-04-16T23:10:56Z
2005-06
Technical Report
CDMTCS Research Reports CDMTCS-269 (2005)
1178-3540
http://hdl.handle.net/2292/3776
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36412012-02-02T23:23:15Zcom_2292_122col_2292_3508
The Poincare-Hardy Inequality on the Complement of a Cantor Set
Calude, C.S
Pavlov, B
The Poincaré–Hardy inequality [see pdf for formula] is derived in R3 on the complement of a Cantor set E. We use a special self-similar tiling and a natural
metric on the space of trajectories generated by a Mauldin–Williams graph which is homeomorphic
with the space of tiles endowed with the Euclidean distance. A crude estimation of the constant K2
is 2,100. Two applications will be briefly discussed. In the last one, the constant K−1 ≈ 0.021819
plays the role of an estimate for the dimensionless Plank constant in the corresponding uncertainty
principle.
2009-04-16T23:10:57Z
2009-04-16T23:10:57Z
2009-04-16T23:10:57Z
2000-05
Technical Report
CDMTCS Research Reports CDMTCS-132 (2000)
1178-3540
http://hdl.handle.net/2292/3641
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38682012-02-02T23:23:14Zcom_2292_122col_2292_3508
Three Criteria for Quantum Random Number Generators Based on Beam Splitters
Svozil, K
We propose three criteria for the generation of random digital strings from quantum beam splitters: (i)
three or more mutually exclusive outcomes corresponding to the invocation of three- and higher dimensional
Hilbert spaces; (ii) the mandatory use of pure states in conjugated bases for preparation and detection; and
(iii) the use of entangled singlet (unique) states for elimination of bias.
2009-04-16T23:10:58Z
2009-04-16T23:10:58Z
2009-04-16T23:10:58Z
2009-04
Technical Report
CDMTCS Research Reports CDMTCS-362 (2009)
1178-3540
http://hdl.handle.net/2292/3868
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38192012-02-02T23:23:15Zcom_2292_122col_2292_3508
On Universal Computably Enumerable Prefix Codes
Calude, C.S
Staiger, L
We study computably enumerable (c.e.) prefix codes which are capable
of coding all positive integers in an optimal way up to a fixed constant:
these codes will be called universal. We prove various characterisations of
these codes including the following one: a c.e. prefix code is universal iff
it contains the domain of a universal self-delimiting Turing machine. Finally,
we study various properties of these codes from the points of view of
computability, maximality, and density.
2009-04-16T23:11:00Z
2009-04-16T23:11:00Z
2009-04-16T23:11:00Z
2007-10
Technical Report
CDMTCS Research Reports CDMTCS-312 (2007)
1178-3540
http://hdl.handle.net/2292/3819
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37462012-02-02T23:23:14Zcom_2292_122col_2292_3508
On Partial Randomness
Calude, C.S
Staiger, L
Terwijn, S.A
[no abstract available]
2009-04-16T23:11:01Z
2009-04-16T23:11:01Z
2009-04-16T23:11:01Z
2004-04
Technical Report
CDMTCS Research Reports CDMTCS-239 (2004)
1178-3540
http://hdl.handle.net/2292/3746
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36062012-02-02T23:23:17Zcom_2292_122col_2292_3508
Unstable Dynamics on a Markov Background and Stability in Average
Kraegeloh, A.M
Dynamical systems which switch between several di erent branches or modes of evolution
via a Markov process are simple mathematical models for irreversible systems. The
averaged evolution for such a dynamics can be obtained by a compression of the corresponding
reversible dynamics onto a coinvariant subspace in the sense of the Lax/Phillips
Scattering Scheme.
If the dynamics switches between some stable modes of evolution and some unstable
modes, still the averaged or expectation evolution might be stable. From the theory
of random evolutions the generator A of the averaged evolution is obtained, and a
de nition of stability in average is suggested. With regard to this context the generator
A is investigated and conditions for stability in average are given for certain special
situations. Based on these results, a conjecture is made about su cient and necessary
conditions for stability in average for some more general cases.
In order to nd hints how to verify or how to modify the conjecture three qualitatively
di erent solvable models are studied. Here the spectral properties of the generators of
all three models are studied, and the results are put in relation to the conjecture.
2009-04-16T23:11:02Z
2009-04-16T23:11:02Z
2009-04-16T23:11:02Z
1999-03
Technical Report
CDMTCS Research Reports CDMTCS-097 (1999)
1178-3540
http://hdl.handle.net/2292/3606
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35952012-02-02T23:23:15Zcom_2292_122col_2292_3508
A Note on Pseudorandom Generators
Calude, C.S
Merkle, W
Wang, Y
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.
2009-04-16T23:11:04Z
2009-04-16T23:11:04Z
2009-04-16T23:11:04Z
1998-05
Technical Report
CDMTCS Research Reports CDMTCS-086 (1998)
1178-3540
http://hdl.handle.net/2292/3595
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37452012-02-02T23:23:16Zcom_2292_122col_2292_3508
The min-max Principle Generalizes Tsirelson's Bound
Filipp, S
Svozil, K
Bounds on the norm of quantum operators associated with classical Bell-type inequalities can be derived from
their maximal eigenvalues. This quantitative method enables detailed predictions of the maximal violations of
Bell-type inequalities.
2009-04-16T23:11:05Z
2009-04-16T23:11:05Z
2009-04-16T23:11:05Z
2004-04
Technical Report
CDMTCS Research Reports CDMTCS-238 (2004)
1178-3540
http://hdl.handle.net/2292/3745
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38182012-02-02T23:23:16Zcom_2292_122col_2292_3508
Design and Evaluation of Slicing Obfuscation
Drape, S
Majumdar, A
The goal of obfuscation is to transform a program, without affecting its functionality,
so that some secret information within the program can be hidden for as
long as possible from an adversary armed with reverse engineering tools. Slicing
is a form of reverse engineering which aims to abstract away a subset of program
code based on a particular program point and is considered to be a potent program
comprehension technique. Thus, slicing could be used as a way of attacking obfuscated
programs. It is challenging to manufacture obfuscating transforms that are
provably resilient to slicing attacks.
We show in this paper how we can utilise the information gained from slicing
a program to aid us in designing obfuscations that are more resistant to slicing.
We extend a previously proposed technique and provide proofs of correctness for
our transforms. Finally, we illustrate our approach with a number of obfuscating
transforms and provide empirical results.
2009-04-16T23:11:07Z
2009-04-16T23:11:07Z
2009-04-16T23:11:07Z
2007-06
Technical Report
CDMTCS Research Reports CDMTCS-311 (2007)
1178-3540
http://hdl.handle.net/2292/3818
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36882012-02-02T23:23:17Zcom_2292_122col_2292_3508
Passages of Proof
Calude, C.S
Calude, E
Marcus, S
In this paper we propose a new perspective on the evolution and history of
the idea of mathematical proof. Proofs will be studied at three levels: syntactical,
semantical and pragmatical. Computer-assisted proofs will be give a special
attention. Finally, in a highly speculative part, we will anticipate the evolution of
proofs under the assumption that the quantum computer will materialize. We will
argue that there is little ‘intrinsic’ difference between traditional and ‘unconventional’
types of proofs.
2009-04-16T23:11:08Z
2009-04-16T23:11:08Z
2009-04-16T23:11:08Z
2002-02
Technical Report
CDMTCS Research Reports CDMTCS-180 (2002)
1178-3540
http://hdl.handle.net/2292/3688
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37202012-02-02T23:23:13Zcom_2292_122col_2292_3508
Randomness Relative to Cantor Expansions
Calude, C.S
Staiger, L
Svozil, K
Imagine a sequence in which the first letter comes from a binary alphabet, the second letter can
be chosen on an alphabet with 10 elements, the third letter can be chosen on an alphabet with
3 elements and so on. Such sequences occur in various physical contexts, in which the coding of
experimental outcome varies with scale. When can such a sequence be called random? In this
paper we offer a solution to the above question using the approach to randomness proposed by
Algorithmic Information Theory.
2009-04-16T23:11:10Z
2009-04-16T23:11:10Z
2009-04-16T23:11:10Z
2003-04
Technical Report
CDMTCS Research Reports CDMTCS-213 (2003)
1178-3540
http://hdl.handle.net/2292/3720
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38462012-02-02T23:23:17Zcom_2292_122col_2292_3508
Simplicity via Provability for Universal Prefix-free Turing Machines
Calude, C.S
Universality is one of the most important ideas in computability theory.
There are various criteria of simplicity for universal Turing machines. Probably the most popular one is to count the number of states/symbols. This
criterion is more complex than it may appear at a first glance. In this note we
review recent results in Algorithmic Information Theory and propose three
new criteria of simplicity for universal prefix-free Turing machines. These
criteria refer to the possibility of proving various natural properties of such
a machine (its universality, for example) in a formal theory, PA or ZFC. In
all cases some, but not all, machines are simple.
2009-04-16T23:11:11Z
2009-04-16T23:11:11Z
2009-04-16T23:11:11Z
2008-11
Technical Report
CDMTCS Research Reports CDMTCS-339 (2008)
1178-3540
http://hdl.handle.net/2292/3846
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38132012-02-02T23:23:14Zcom_2292_122col_2292_3508
Quantum Informatics and the Relations Between Informatics, Physics and Mathematics: A Dialogue
Calude, C.S
Gruska, J
[no abstract available]
2009-04-16T23:11:12Z
2009-04-16T23:11:12Z
2009-04-16T23:11:12Z
2007-05
Technical Report
CDMTCS Research Reports CDMTCS-306 (2007)
1178-3540
http://hdl.handle.net/2292/3813
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35452012-02-02T23:23:14Zcom_2292_122col_2292_3508
Embedding Quantum Universes into Classical Ones
Calude, C.S
Hertling, P.H
Svozil, K
Do the partial order and lattice operations of a quantum logic correspond to the
logical implication and connectives of classical logic? Re-phrased, how far might a
classical understanding of quantum mechanics be, in principle, possible? A celebrated
result by Kochen and Specker answers the above question in the negative. However,
this answer is just one among different possible ones, not all negative. It is our aim
to discuss the above question in terms of mappings of quantum worlds into classical
ones, more specifically, in terms of embeddings of quantum logics into classical logics;
depending upon the type of restrictions imposed on embeddings the question may get
negative or positive answers.
2009-04-16T23:11:15Z
2009-04-16T23:11:15Z
2009-04-16T23:11:15Z
1997-05
Technical Report
CDMTCS Research Reports CDMTCS-036 (1997)
1178-3540
http://hdl.handle.net/2292/3545
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37942012-02-02T23:23:16Zcom_2292_122col_2292_3508
Probability Calculations Under the IAC Hypothesis
Pritchard, G
Wilson, Mark
We show how powerful algorithms recently developed for counting lattice points
and computing volumes of convex polyhedra can be used to compute probabilities
of a wide variety of events of interest in social choice theory. Several illustrative
examples are given.
2009-04-16T23:11:16Z
2009-04-16T23:11:16Z
2009-04-16T23:11:16Z
2006-10
Technical Report
CDMTCS Research Reports CDMTCS-287 (2006)
1178-3540
http://hdl.handle.net/2292/3794
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38142020-03-10T02:14:36Zcom_2292_122col_2292_3508
Asymptotics of Diagonal Coefficients of Multivariate Generating Functions
Raichev, A
Wilson, Mark
This article presents some recent progress in the asymptotics of diagonal coefficients
of multivariate generating functions and can be seen as an extension of [RW].
2009-04-16T23:11:17Z
2009-04-16T23:11:17Z
2009-04-16T23:11:17Z
2007-05
Technical Report
CDMTCS Research Reports CDMTCS-307 (2007)
1178-3540
http://hdl.handle.net/2292/3814
CDMTCS Research Report Series
28368
6233
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35902012-02-02T23:23:18Zcom_2292_122col_2292_3508
On Hypersimple Sets and Chaitin Complexity
Arslanov, A
In this paper we study some computability theoretic properties of two notions of
randomness for finite strings: randomness based on the blank-endmarker complexity measure
and Chaitin randomness based on the self-delimiting complexity measure. For example, we find
the position of RANDK and RANDC at the same level in the scale of immunity notions by
proving that both of them are not hyperimmune sets. Also we introduce a new notion of complex
infinite sequences of finite strings. We call them K-bounded sequences.
2009-04-16T23:11:19Z
2009-04-16T23:11:19Z
2009-04-16T23:11:19Z
1998-04
Technical Report
CDMTCS Research Reports CDMTCS-081 (1998)
1178-3540
http://hdl.handle.net/2292/3590
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36662012-02-02T23:23:17Zcom_2292_122col_2292_3508
Relations Between the Low Subrecursion Classes
Grozea, C
[no abstract available]
2009-04-16T23:11:20Z
2009-04-16T23:11:20Z
2009-04-16T23:11:20Z
2001-07
Technical Report
CDMTCS Research Reports CDMTCS-158 (2001)
1178-3540
http://hdl.handle.net/2292/3666
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35472012-02-02T23:23:13Zcom_2292_122col_2292_3508
A Constructive Proof of Gleason's Theorem
Richman, F
Bridges, D.S
Gleason's theorem states that any totally additive measure on the closed subspaces,
or projections, of a Hilbert space of dimension greater than two is given by a positive
operator of trace class. In this paper we give a constructive proof of that theorem.
A measure μ on the projections of a real or complex Hilbert space assigns to
each projection P a nonnegative real number μ(P) such that if σ = ∑Pi, where the
Pi are mutually orthogonal, then μ(σ) =∑μ(Pi). Such a measure is determined by
its values on the one-dimensional projections. Let W be the measure of the identity
projection, and Px the projection onto the 1-dimensional space spanned by the unit
vector x. Then the measure μ is determined by the real-valued function f(x) = μ(Px)
on the unit sphere, a function which has the property that [see pdf for formula] for each orthonormal basis E. Gleason calls such a function f a frame function of
weight W. If T is a positive operator of trace class, then f(x) = ‹Tx,x› is a frame
function. Gleason's theorem is that every frame function arises in this way.
The original reference for Gleason's theorem is [4], which can also be found in
Hooker [6]. Cooke, Keane and Moran [3] gave a proof that is elementary in the sense
that it does not appeal to the theory of representations of the orthogonal group,
which the original proof does. However, some of the reasoning in [3] seems hopelessly
nonconstructive, so we follow the general outline of [4] until we come to the end of
the 3-dimensional real case, at which point we modify some arguments in [3] rather
than attempt a constructive development of the necessary representation theory.
Any Hermitian form B on a finite-dimensional inner product space gives rise to a
frame function f(x) = B(x; x) whose weight is equal to the trace of the matrix of B.
The essence of Gleason's theorem is the following converse. -- from Introduction
2009-04-16T23:11:22Z
2009-04-16T23:11:22Z
2009-04-16T23:11:22Z
1997-05
Technical Report
CDMTCS Research Reports CDMTCS-038 (1997)
1178-3540
http://hdl.handle.net/2292/3547
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36692012-02-02T23:23:17Zcom_2292_122col_2292_3508
The Bridge Crossing Problem: Draft Form
Calude, C.S
Calude, E
In this note we solve the general case of the Bridge Crossing Problem.
2009-04-16T23:11:24Z
2009-04-16T23:11:24Z
2009-04-16T23:11:24Z
2001-09
Technical Report
CDMTCS Research Reports CDMTCS-161 (2001)
1178-3540
http://hdl.handle.net/2292/3669
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35992012-02-02T23:23:13Zcom_2292_122col_2292_3508
Degree-Theoretic Aspects of Computably Enumerable Reals
Calude, C.S
Coles, R.J
Hertling, P.H
Khoussainov, B
A real α is computable if its left cut, L(α); is computable. If (qi)i
is a computable sequence of rationals computably converging to α,
then {qi}, the corresponding set, is always computable. A computably
enumerable (c.e.) real is a real which is the limit of an increasing
computable sequence of rationals, and has a left cut which is c.e. We
study the Turing degrees of representations of c.e. reals, that is the
degrees of increasing computable sequences converging to α. For example, every representation A of α is Turing reducible to L(α). Every noncomputable c.e. real has both a computable and noncomputable
representation. In fact, the representations of noncomputable c.e. re-
als are dense in the c.e. Turing degrees, and yet not every c.e. Turing
degree below degT L(α) necessarily contains a representation of α.
2009-04-16T23:11:25Z
2009-04-16T23:11:25Z
2009-04-16T23:11:25Z
1998-09
Technical Report
CDMTCS Research Reports CDMTCS-090 (1998)
1178-3540
http://hdl.handle.net/2292/3599
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37502012-02-02T23:23:15Zcom_2292_122col_2292_3508
Inexpensive Linear-Optical Implementations of Deutsch's Algorithm
Stay, M
Deutsch’s algorithm was the first algorithm proposed for which quantum computers
could outperform classical computers. It requires only a single qubit; since photons make
very stable qubits, and expensive materials are only needed for multi-qubit gates, one can
implement Deutsch’s algorithm using inexpensive, readily available parts. Here we
describe two implementations. Such a computer can be useful in demonstrating simple
quantum effects.
2009-04-16T23:11:26Z
2009-04-16T23:11:26Z
2009-04-16T23:11:26Z
2004-07
Technical Report
CDMTCS Research Reports CDMTCS-243 (2004)
1178-3540
http://hdl.handle.net/2292/3750
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37142012-02-02T23:23:14Zcom_2292_122col_2292_3508
Games on Graphs: Automata, Structure, and Complexity
Khoussainov, B
Kowalski, T
McNaughton in his known paper [7], motivated by the work of Gurevich and
Harrington [4], introduced a class of games played on finite graphs. In his paper
McNaughton proves that winners in his games have winning strategies that can
be implemented by finite state automata. McNaughton games have attracted
attention of many experts in the area, partly because the games have close
relationship with automata theory, the study of reactive systems, and logic (see,
for instance, [12] and [11]). McNaughton games can also be used to develop
game-theoretical approach for many important concepts in computer science
such as models for concurrency, communication networks, and update networks,
and provide natural examples of computational problems. For example, Nerode,
Remmel and Yakhnis in a series of papers (e.g., [8], [9]) developed foundations of
concurrent programming in which finite state strategies of McNaughton games
are identified with distributed concurrent programs. -- from Introduction
2009-04-16T23:11:28Z
2009-04-16T23:11:28Z
2009-04-16T23:11:28Z
2003-01
Technical Report
CDMTCS Research Reports CDMTCS-207 (2003)
1178-3540
http://hdl.handle.net/2292/3714
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35482012-02-02T23:23:16Zcom_2292_122col_2292_3508
A Genius' Story: Two Books on Godel
Calude, C.S
Undoubtly, Gödel was the greatest logician of the twentieth century. There is no trace
of exaggeration in saying, following Wang, that Gödel's contribution to mathematics has the
same status as Freudian psychology, Einstein's theory of relativity, Bohr's principle of complementarity,
Heisenberg's uncertainty principle, keynesian economics, and Watson and Crick
double helix model of DNA. Yet, with a few notable exceptions, most of the personal details
of Gödel's life remained a mystery
2009-04-16T23:11:29Z
2009-04-16T23:11:29Z
2009-04-16T23:11:29Z
1997-06
Technical Report
CDMTCS Research Reports CDMTCS-039 (1997)
1178-3540
http://hdl.handle.net/2292/3548
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36232012-02-02T23:23:13Zcom_2292_122col_2292_3508
Chaitin $\Omega$ Numbers, Solovay Machines, and Incompleteness
Calude, C.S
Computably enumerable (c.e.) reals can be coded by Chaitin machines through
their halting probabilities. Tuning Solovay's construction of a Chaitin universal machine
for which ZFC (if arithmetically sound) cannot determine any single bit of the
binary expansion of its halting probability, we show that every c.e. random real is the
halting probability of a universal Chaitin machine for which ZFC cannot determine
more than its initial block of 1 bits – as soon as you get a 0 it's all over. Finally,
a constructive version of Chaitin information-theoretic incompleteness theorem is
proven.
2009-04-16T23:11:31Z
2009-04-16T23:11:31Z
2009-04-16T23:11:31Z
1999-10
Technical Report
CDMTCS Research Reports CDMTCS-114 (1999)
1178-3540
http://hdl.handle.net/2292/3623
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37672012-02-02T23:23:17Zcom_2292_122col_2292_3508
Quasi-Apartness and Neighbourhood Spaces
Ishihara, H
Mines, R
Schuster, P
Vita, L.S
We extend the concept of apartness spaces to the concept of quasi-apartness spaces. We show that there is an adjunction between the category of quasi-apartness spaces and the category of neighbourhood spaces, which indicates that quasi-apartness is a more natural concept than apartness. We also show that there is an adjoint equivalence between the category of apartness spaces and the category of Grayson’s separated spaces.
2009-04-16T23:11:32Z
2009-04-16T23:11:32Z
2009-04-16T23:11:32Z
2005-03
Technical Report
CDMTCS Research Reports CDMTCS-260 (2005)
1178-3540
http://hdl.handle.net/2292/3767
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37532012-02-02T23:23:13Zcom_2292_122col_2292_3508
Computing with Cells and Atoms: After Five Years
Calude, C.S
Paun, G
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.
2009-04-16T23:11:33Z
2009-04-16T23:11:33Z
2009-04-16T23:11:33Z
2004-08
Technical Report
CDMTCS Research Reports CDMTCS-246 (2004)
1178-3540
http://hdl.handle.net/2292/3753
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36922012-02-02T23:23:17Zcom_2292_122col_2292_3508
n-ary Quantum Information Defined by State Partitions
Svozil, K
We define a measure of quantum information which is based on state partitions. Properties of this measure for entangled
many-particle states are discussed. k particles specify k “nits” in such a way that k mutually commuting measurements of
n-ary observables are necessary to determine the information.
2009-04-16T23:11:35Z
2009-04-16T23:11:35Z
2009-04-16T23:11:35Z
2002-05
Technical Report
CDMTCS Research Reports CDMTCS-184 (2002)
1178-3540
http://hdl.handle.net/2292/3692
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37482012-02-02T23:23:17Zcom_2292_122col_2292_3508
Is Complexity a Source of Incompleteness?
Calude, C.S
Juergensen, H
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.
2009-04-16T23:11:36Z
2009-04-16T23:11:36Z
2009-04-16T23:11:36Z
2004-06
Technical Report
CDMTCS Research Reports CDMTCS-241 (2004)
1178-3540
http://hdl.handle.net/2292/3748
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35972020-03-09T01:54:14Zcom_2292_122col_2292_3508
The Hausdorff Measure of Regular Omega-Languages is Computable
Staiger, L
In several previous papers we have shown how to calculate Hausdor
dimension and measure for certain classes of regular ω-languages
(cf. [MS94], [St89], and [St93]). In this note we show that the results obtained in the papers [MS94] and [St93] can be used to give
an effective procedure for the calculation of the Hausdor
measure for
arbitrary regular ω-languages.
2009-04-16T23:11:38Z
2009-04-16T23:11:38Z
2009-04-16T23:11:38Z
1998-08
Technical Report
CDMTCS Research Reports CDMTCS-088 (1998)
1178-3540
http://hdl.handle.net/2292/3597
CDMTCS Research Report Series
33898
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35942012-02-02T23:23:15Zcom_2292_122col_2292_3508
Search and Enumeration Techniques for Incidence Structures
Denny, P.C
This thesis investigates a number of probabilistic and exhaustive computational search
techniques for the construction of a wide variety of combinatorial designs, and in particular,
incidence structures. The emphasis is primarily from a computer science perspective, and
focuses on the algorithmic development of the techniques, taking into account running time
considerations and storage requirements. The search and enumeration techniques developed
in this thesis have led to the discovery of a number of new results in the field of
combinatorial design theory.
2009-04-16T23:11:39Z
2009-04-16T23:11:39Z
2009-04-16T23:11:39Z
1998-05
Technical Report
CDMTCS Research Reports CDMTCS-085 (1998)
1178-3540
http://hdl.handle.net/2292/3594
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36942012-02-02T23:23:13Zcom_2292_122col_2292_3508
Implementing Bead--Sort with P systems
Arulanandham, J.J
In this paper, we implement Bead-Sort, a natural sorting algorithm we introduced in [1], with the new, biochemically inspired P systems. We make use of a special type of P system – a tissue P system that computes by means of communication (using symport/antiport rules) only.
2009-04-16T23:11:41Z
2009-04-16T23:11:41Z
2009-04-16T23:11:41Z
2002-05
Technical Report
CDMTCS Research Reports CDMTCS-186 (2002)
1178-3540
http://hdl.handle.net/2292/3694
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35722012-02-02T23:23:13Zcom_2292_122col_2292_3508
Disjunctive Sequences: An Overview
Calude, C.S
Priese, L
Staiger, L
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.
2009-04-16T23:11:42Z
2009-04-16T23:11:42Z
2009-04-16T23:11:42Z
1997-10
Technical Report
CDMTCS Research Reports CDMTCS-063 (1997)
1178-3540
http://hdl.handle.net/2292/3572
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36892012-02-02T23:23:13Zcom_2292_122col_2292_3508
Computable Isomorphism of Boolean Algebras with Operators
Khoussainov, B
Kowalski, T
One of the central topics in computable algebra and model theory is concerned with the study of
computable isomorphisms. Classically, we do not distinguish between isomorphic structures, however, from
computability point of view, isomorphic structures can differ quite dramatically. A typical example is
provided by the linear order of type ω. It has two computable copies such that in one the successor function
is computable, but it is not computable in the other. These are clearly classically isomorphic, but they are
not computably isomorphic.
2009-04-16T23:11:44Z
2009-04-16T23:11:44Z
2009-04-16T23:11:44Z
2002-03
Technical Report
CDMTCS Research Reports CDMTCS-181 (2002)
1178-3540
http://hdl.handle.net/2292/3689
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35262012-02-02T23:23:14Zcom_2292_122col_2292_3508
Randomness, Computability, and Algebraic Specifications
Khoussainov, B
[no abstract available]
2009-04-16T23:11:45Z
2009-04-16T23:11:45Z
2009-04-16T23:11:45Z
1996-08
Technical Report
CDMTCS Research Reports CDMTCS-017 (1996)
1178-3540
http://hdl.handle.net/2292/3526
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37252012-02-02T23:23:15Zcom_2292_122col_2292_3508
Generalisations of Disjunctive Sequences
Calude, C.S
Staiger, L
The present paper proposes a generalisation of the notion of disjunctive (or rich) sequence, that is, of an infinite
sequence of letters having each finite sequence as a subword. Our aim is to give a reasonable notion of disjunctiveness
relative to a given set of sequences F. We show that a definition like “every subword which occurs
at infinitely many different positions in sequences in F has to occur infinitely often in the sequence” fulfils
properties similar to the original unrelativised notion of disjunctiveness. Finally, we investigate our concept of
generalised disjunctiveness in spaces of Cantor expansions of reals.
2009-04-16T23:11:47Z
2009-04-16T23:11:47Z
2009-04-16T23:11:47Z
2003-06
Technical Report
CDMTCS Research Reports CDMTCS-218 (2003)
1178-3540
http://hdl.handle.net/2292/3725
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36392012-02-02T23:23:17Zcom_2292_122col_2292_3508
Reflections on Quantum Computing
Calude, C.S
Dinneen, Michael
Svozil, K
In this rather speculative note three problems pertaining to the power
and limits of quantum computing are posed and partially answered: a)
when are quantum speedups possible?, b) is fixed-point computing a better
model for quantum computing?, c) can quantum computing trespass
the Turing barrier?
2009-04-16T23:11:48Z
2009-04-16T23:11:48Z
2009-04-16T23:11:48Z
2000-03
Technical Report
CDMTCS Research Reports CDMTCS-130 (2000)
1178-3540
http://hdl.handle.net/2292/3639
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36872012-02-02T23:23:17Zcom_2292_122col_2292_3508
Logical Equivalence Between Generalized Urn Models and Finite Automata
Svozil, K
To every generalized urn model there exists a finite (Mealy) automaton with identical
propositional calculus. The converse is true as well.
2009-04-16T23:11:49Z
2009-04-16T23:11:49Z
2009-04-16T23:11:49Z
2002-02
Technical Report
CDMTCS Research Reports CDMTCS-179 (2002)
1178-3540
http://hdl.handle.net/2292/3687
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35652012-02-02T23:23:16Zcom_2292_122col_2292_3508
Paradise Lost, or Paradise Regained?
Bridges, D.S
Dediu, L.S
This paper outlines some of the history and philosophy of constructive mathematics, concentrating on the work of the late Errett Bishop and his followers.
2009-04-16T23:11:51Z
2009-04-16T23:11:51Z
2009-04-16T23:11:51Z
1997-09
Technical Report
CDMTCS Research Reports CDMTCS-056 (1997)
1178-3540
http://hdl.handle.net/2292/3565
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35402012-02-02T23:23:13Zcom_2292_122col_2292_3508
Computable Isomorphisms, Degree Spectra of Relations, and Scott Families
Khoussainov, B
Shore, R.A
In studying effective structures we investigate the effective content of typical notions and
constructions in many branches of mathematics including universal algebra and model theory.
In particular, we are interested in the possibilities of effectivizing model-theoretic or algebraic
constructions and the limits on these possibilities. For instance, we try to understand whether
certain results of model theory (or universal algebra) can be carried out effectively. If not,
we then try to discover sharp effective counterexamples.
The systematic study of effectiveness in algebraic structures goes back to pioneering
papers by Frölich and Shepherdson [11], Malcev [28][29], and Rabin [34] in the early 60s.
Later in the early 70s, Nerode and his collaborators initiated combining algebraic constructions
with priority arguments from computability theory thus beginning a new era in the
development of the subject.
Nowadays, there various approaches to effectiveness in structures. For example, Cenzer,
Nerode, Remmel have been developing theory of p-time structures [6]. Khoussainov and
Nerode have began the development of the theory of automatic structures [27]. In this paper
we are interested in those structures in which the basic computations can be performed by
Turing machines.
2009-04-16T23:11:52Z
2009-04-16T23:11:52Z
2009-04-16T23:11:52Z
1997-04
Technical Report
CDMTCS Research Reports CDMTCS-031 (1997)
1178-3540
http://hdl.handle.net/2292/3540
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36682012-02-02T23:23:17Zcom_2292_122col_2292_3508
LifeTime: A Unified Study of Life (A Preliminary Version)
Meyerstein, F.W
Moller, A.P
[no abstract available]
2009-04-16T23:11:54Z
2009-04-16T23:11:54Z
2009-04-16T23:11:54Z
2001-09
Technical Report
CDMTCS Research Reports CDMTCS-160 (2001)
1178-3540
http://hdl.handle.net/2292/3668
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37522012-02-02T23:23:19Zcom_2292_122col_2292_3508
Fitting Parameters for a Solvable Model of a Quantum Network (CDMTCS)
Harmer, M.
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.
2009-04-16T23:11:55Z
2009-04-16T23:11:55Z
2009-04-16T23:11:55Z
2004-07
Technical Report
CDMTCS Research Reports CDMTCS-245 (2004)
1178-3540
http://hdl.handle.net/2292/3752
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36112012-02-02T23:23:16Zcom_2292_122col_2292_3508
P Systems with Active Membranes: Attacking NP Complete Problems
Paun, G
P systems are parallel Molecular Computing models based on processing multisets of objects in cell-like membrane structures. Various variants were already
shown to be computationally universal, equal in power to Turing machines. In this
paper one proposes a class of P systems whose membranes are the main active
components, in the sense that they directly mediate the evolution and the communication of objects. Moreover, the membranes can multiply themselves by division.
We prove that this variant is not only computationally universal, but also able to
solve NP complete problems in polynomial (actually, linear) time. We exemplify
this assertion with the well-known SAT problem.
2009-04-16T23:11:57Z
2009-04-16T23:11:57Z
2009-04-16T23:11:57Z
1999-05
Technical Report
CDMTCS Research Reports CDMTCS-102 (1999)
1178-3540
http://hdl.handle.net/2292/3611
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37152012-02-02T23:23:13Zcom_2292_122col_2292_3508
Automatic linear orders and trees (Revised)
Khoussainov, B
Rubin, S
Stephan, F
We investigate partial orders that are computable, in a precise sense, by finite automata. Our emphasis is on trees and linear orders. We study the relationship between automatic linear orders and trees in terms of rank functions that are related to Cantor-Bendixson rank. We prove that automatic linear orders and automatic trees have finite rank. As an application we provide a procedure for deciding the isomorphism problem for automatic ordinals. We also investigate the complexity and definability of infinite paths in automatic trees. In particular we show that every infinite path in an automatic tree with countably many infinite paths is a regular language.
2009-04-16T23:11:58Z
2009-04-16T23:11:58Z
2009-04-16T23:11:58Z
2003-11
Technical Report
CDMTCS Research Reports CDMTCS-208 (2003)
1178-3540
http://hdl.handle.net/2292/3715
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36812012-02-02T23:23:17Zcom_2292_122col_2292_3508
Some Computability-Theoretical Aspects of Reals and Randomness
Downey, R.G
We study computably enumerable reals (i.e. their left cut is computably
enumerable) in terms of their spectra of representations and presentations. Then we study
such objects in terms of algorithmic randomness, culminating in some recent work of the
author with Hirschfeldt, Laforte, and Nies concerning methods of calibrating randomness.
2009-04-16T23:12:00Z
2009-04-16T23:12:00Z
2009-04-16T23:12:00Z
2002-01
Technical Report
CDMTCS Research Reports CDMTCS-173 (2002)
1178-3540
http://hdl.handle.net/2292/3681
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37262012-02-02T23:23:13Zcom_2292_122col_2292_3508
Dialogues on Quantum Computing
Calude, C.S
What sort of machines do useful computation in a universe described by classical mechanics?
The answer was provided in 1936 by the British mathematician Alan Turing,
and it’s known today as the Turing machine. But even in 1936 classical mechanics was
known to be false, and so one could have asked the question: What sort of machines do
useful computation in a universe described by quantum mechanics? In a trivial sense,
everything is a quantum computer. A pebble is a quantum computer for calculating the
constant-position function; current computers exploit quantum effects (like electrons
tunneling through barriers) to control computation and to be able to run fast. But
quantum computing is much more than that. In what follows we will present – in the
form of a biased, informal dialogue – a few key-ideas on quantum computing.
2009-04-16T23:12:01Z
2009-04-16T23:12:01Z
2009-04-16T23:12:01Z
2003-06
Technical Report
CDMTCS Research Reports CDMTCS-219 (2003)
1178-3540
http://hdl.handle.net/2292/3726
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35782012-02-02T23:23:13Zcom_2292_122col_2292_3508
Adjoints, Absolute Values and Polar Decompostions
Bridges, D.S
Richman, F
Schuster, P
Various questions about adjoints, absolute values and polar
decompositions of operators are addressed from a constructive point of view.
The focus is on bilinear forms. Conditions are given for the existence of an
adjoint, and a general notion of a polar decomposition is developed. The Riesz
representation theorem is proved without countable choice.
2009-04-16T23:12:02Z
2009-04-16T23:12:02Z
2009-04-16T23:12:02Z
1997-11
Technical Report
CDMTCS Research Reports CDMTCS-069 (1997)
1178-3540
http://hdl.handle.net/2292/3578
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36122012-02-02T23:23:13Zcom_2292_122col_2292_3508
Variable-Length Codes for Sources with Equiprobable Symbols
Assanovich, B
Gunther, Ulrich
Variable-length codes can provide compression for data communication. Such codes may be
used not only when the source statistics is known but also when we do not know the source
probability distribution, and a source with equal symbol probabilities (equiprobable symbols)
can or has to be assumed. This paper presents variable-length codes with code words that differ
in length by at most one code symbol. Such codes suit the efficient encoding of sources with
equiprobable symbols. We accommodate non-binary codes and present an iterative algorithm
for the construction of such codes. We also calculate the average codeword length for such
codes, which extends Krichevski's result for binary codes [5]. Finally, we propose a scheme that
allows the code to be communicated efficiently from transmitter to receiver.
2009-04-16T23:12:04Z
2009-04-16T23:12:04Z
2009-04-16T23:12:04Z
1999-05
Technical Report
CDMTCS Research Reports CDMTCS-103 (1999)
1178-3540
http://hdl.handle.net/2292/3612
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/36212012-02-02T23:23:15Zcom_2292_122col_2292_3508
Solving Problems with Finite Test Sets
Calude, C.S
Juergensen, H
Legg, S
Every finite and every co-finite set of non-negative integers is decidable. This is
true and it is not, depending on whether the set is given constructively. A similar
constraint is applicable in language theory and many other fields. The constraint is
usually understood and, hence, omitted.
The phenomenon of a set being finite, but possibly undecidable, is, of course,
a consequence of allowing non-constructive arguments in proofs. In this note we
discuss a few ramifications of this fact. We start out with showing that every number
theoretic statement that can be expressed in first-order logic can be reduced to a finite set, to be called a test set. Thus, if one knew the test set, one could determine
the truth of the statement. The crucial point is, of course, that we may not able to
know what the finite test set is. Using problems in the class II1 of the arithmetic
hierarchy as an example, we establish that the bound on the size of the test set is
Turing-complete and that it is upper-bounded by the busy-beaver function.
This re-enforces the fact that there is a vast difference between finiteness and
constructive finiteness. In the context of the present re-opened discussion about the
notion of computability – possibly extending its realm through new computational
models derived from physics – the constraint of constructivity of the model itself
may add another twist.
2009-04-16T23:12:06Z
2009-04-16T23:12:06Z
2009-04-16T23:12:06Z
1999-09
Technical Report
CDMTCS Research Reports CDMTCS-112 (1999)
1178-3540
http://hdl.handle.net/2292/3621
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38212012-02-02T23:23:13Zcom_2292_122col_2292_3508
The Underlying Optimal Protocol of Rule 218 Cellular Automaton
Goles, E
Littleland, Cedric
Rapaport, I
2009-04-16T23:12:07Z
2009-04-16T23:12:07Z
2009-04-16T23:12:07Z
2007-11
Technical Report
CDMTCS Research Reports CDMTCS-314 (2007)
1178-3540
http://hdl.handle.net/2292/3821
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/37402012-02-02T23:23:15Zcom_2292_122col_2292_3508
Quantum Information via State Partitions and the Context Transition Principle
Svozil, K
For many–particle systems, quantum information in base n can be defined by
partitioning the set of states according to the outcomes of n–ary (joint) observables.
Thereby, k particles can carry k nits. With regards to the randomness of single
outcomes, a context translation principle is proposed. Quantum randomness is
related to the uncontrollable degrees of freedom of the measurement interface,
thereby translating a mismatch between the state prepared and the state measured.
2009-04-16T23:12:09Z
2009-04-16T23:12:09Z
2009-04-16T23:12:09Z
2004-01
Technical Report
CDMTCS Research Reports CDMTCS-233 (2004)
1178-3540
http://hdl.handle.net/2292/3740
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/35282012-02-02T23:23:14Zcom_2292_122col_2292_3508
Forbidden Minors to Graphs with Small Feedback Sets
Dinneen, Michael
Cattell, K
Fellows, M.R
Finite obstruction set characterizations for lower ideals in the minor order are guaran-
teed to exist by the Graph Minor Theorem. In this paper we characterize several families of
graphs with small feedback sets, namely k
1-Feedback Vertex Set, k
2-Feedback Edge
Set and (k
1,k
2){Feedback Vertex/Edge Set, for small integer parameters k
1 and k
2.
Our constructive methods can compute obstruction sets for any minor-closed family of
graphs, provided the pathwidth (or treewidth) of the largest obstruction is known.
2009-04-16T23:12:10Z
2009-04-16T23:12:10Z
2009-04-16T23:12:10Z
1996-10
Technical Report
CDMTCS Research Reports CDMTCS-019 (1996)
1178-3540
http://hdl.handle.net/2292/3528
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38352012-02-02T23:23:15Zcom_2292_122col_2292_3508
Every Computably Enumerable Random Real Is Provably Computably Enumerable Random
Calude, C.S
Hay, N.J
We prove that every computably enumerable (c.e.) random real is provable in
Peano Arithmetic (PA) to be c.e. random, a statement communicated to one author
by B. Solovay. A major step in the proof is to show that the theorem stating that “a
real is c.e. and random iff it is the halting probability of a universal prefix-free Turing
machine" can be proven in PA. Our proof, which is simpler than the standard one, can
also be used for the original theorem.
The result that every c.e. random real is provably c.e. random is in contrast with
the case of computable functions, where not every computable function is provably
computable. It is even more interesting to compare this result with the fact that – in general – random finite strings are not provably random.
The paper also includes a sharper form of the Kraft-Chaitin Theorem, as well as an
automatic proof of this theorem written with the interactive theorem prover Isabelle.
2009-04-16T23:12:12Z
2009-04-16T23:12:12Z
2009-04-16T23:12:12Z
2008-07
Technical Report
CDMTCS Research Reports CDMTCS-328 (2008)
1178-3540
http://hdl.handle.net/2292/3835
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38362012-02-02T23:23:19Zcom_2292_122col_2292_3508
A New Linear-Time Dominating Number Algorithm for Graphs of Bounded Pathwidth
Dinneen, Michael
Fenton, A.J.L
We present a simple algorithm for determining the minimum dominating
number of any graph of bounded pathwidth. The algorithm has running time
O(3t+1n) where n is the size of the graph and t is a fixed pathwidth bound.
We also present an implementation in Python of this algorithm extended to
handle graphs of bounded treewidth.
2009-04-16T23:12:13Z
2009-04-16T23:12:13Z
2009-04-16T23:12:13Z
2008-07
Technical Report
CDMTCS Research Reports CDMTCS-329 (2008)
1178-3540
http://hdl.handle.net/2292/3836
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
oai:researchspace.auckland.ac.nz:2292/38052012-02-02T23:23:15Zcom_2292_122col_2292_3508
Prefix-free Lukasiewicz Languages
Staiger, L
Generalised Łukasiewicz languages are simply described languages having
good information-theoretic properties. An especially desirable property is
the one of being a prefix code. This paper addresses the question under which
conditions a generalised Łukasiewicz language is a prefix code. Moreover, an
upper bound on the delay of decipherability of a generalised Łukasiewicz language
is derived.
2009-04-16T23:12:15Z
2009-04-16T23:12:15Z
2009-04-16T23:12:15Z
2007-01
Technical Report
CDMTCS Research Reports CDMTCS-298 (2007)
1178-3540
http://hdl.handle.net/2292/3805
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
Department of Computer Science, The University of Auckland, New Zealand
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
qdc///col_2292_3508/100