2020-07-10T00:52:26Z
https://researchspace.auckland.ac.nz/dspace-oai/request
oai:researchspace.auckland.ac.nz:2292/3509
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Gibbons, Jenny
2009-04-14T23:08:28Z
2009-04-14T23:08:28Z
1995-04
CDMTCS Research Report Series CDMTCS-001 (1995)
http://hdl.handle.net/2292/3509
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.
Submitted by Vanessa Newton-Wade (v.newton-wade@auckland.ac.nz) on 2009-04-14T23:08:28Z
No. of bitstreams: 1
001damgs.pdf: 239662 bytes, checksum: 85d29aa43a9a0386b6be6dc1798d07f1 (MD5)
Made available in DSpace on 2009-04-14T23:08:28Z (GMT). No. of bitstreams: 1
001damgs.pdf: 239662 bytes, checksum: 85d29aa43a9a0386b6be6dc1798d07f1 (MD5)
Previous issue date: 1995-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
An initial-algebra approach to directed acyclic graphs
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
LICENSE
license.txt
license.txt
text/plain
3638
https://researchspace.auckland.ac.nz/bitstream/2292/3509/1/license.txt
cb1b67627a13b57645adb3a8d4499d2f
MD5
1
ORIGINAL
001damgs.pdf
001damgs.pdf
application/pdf
239662
https://researchspace.auckland.ac.nz/bitstream/2292/3509/2/001damgs.pdf
85d29aa43a9a0386b6be6dc1798d07f1
MD5
2
TEXT
001damgs.pdf.txt
001damgs.pdf.txt
text/plain
47197
https://researchspace.auckland.ac.nz/bitstream/2292/3509/3/001damgs.pdf.txt
1d7b7582e444e8f153995e9479baf7c0
MD5
3
2292/3509
oai:researchspace.auckland.ac.nz:2292/3509
2012-02-03 12:23:13.296
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
TGljZW5zZSBncmFudGVkIGJ5IFZhbmVzc2EgTmV3dG9uLVdhZGUgKHYubmV3dG9uLXdhZGVAYXVja2xhbmQuYWMubnopIG9uIDIwMDktMDQtMTRUMjM6MDY6MThaIChHTVQpOgoKPHA+RGVwb3NpdCBMaWNlbmNlIC0gU3VtbWFyeSAtIFJlc2VhcmNoU3BhY2U8L3A+CjxwPlN1bW1hcnkgb2YgRGVwb3NpdCBMaWNlbmNlIGZvciBUaGUgVW5pdmVyc2l0eSBvZiBBdWNrbGFuZCBMaWJyYXJ5J3MKZGlnaXRhbCByZXBvc2l0b3J5IGZvciByZXNlYXJjaCBjdXJyZW50bHkgY2FsbGVkIFJlc2VhcmNoU3BhY2UgYW5kCmxvY2F0ZWQgYXQgd3d3LnJlc2VhcmNoc3BhY2UuYXVja2xhbmQuYWMubnoKPC9wPjxwPgpXb3JrIGRlcG9zaXRlZCBhbmQgc3RvcmVkIGluIFJlc2VhcmNoU3BhY2UgaXMgcmVzdHJpY3RlZCB0byBSZXNlYXJjaApPdXRwdXRzIGNyZWF0ZWQgYnkgbWVtYmVycyBvZiBUaGUgVW5pdmVyc2l0eSBvZiBBdWNrbGFuZCwgaW5jbHVkaW5nIApqb3VybmFsIGFydGljbGVzLCBjb25mZXJlbmNlIHBhcGVycywgcmVzZWFyY2gvdGVjaG5pY2FsIHJlcG9ydHMsIG9yCm90aGVyIHJlc2VhcmNoIG1hdGVyaWFscy4KPC9wPjxwPllvdXIgcmlnaHRzIGFuZCBDb25kaXRpb25zIG9mIERlcG9zaXQKPC9wPjxwPkJ5IGRlcG9zaXRpbmcgdGhlIFdvcmsgaW4gVGhlIFVuaXZlcnNpdHkgb2YgQXVja2xhbmQgTGlicmFyeSdzCmRpZ2l0YWwgcmVwb3NpdG9yeSBmb3IgcmVzZWFyY2gsIFJlc2VhY2hTcGFjZSwgSSBncmFudCBUaGUgVW5pdmVyc2l0eQpvZiBBdWNrbGFuZCBhIG5vbi1leGNsdXNpdmUgbGljZW5jZSB0byBjb3B5LCB0cmFuc2xhdGUgdG8gYW55IG1lZGl1bQpvciBmb3JtYXQgKGZvciB0aGUgcHVycG9zZSBvZiBwcmVzZXJ2YXRpb24gb3IgbWlncmF0aW9uKSwgYW5kL29yCmNvbW11bmljYXRlIHRoZSBXb3JrIChpbmNsdWRpbmcgdGhlIGFic3RyYWN0KSB3b3JsZHdpZGUgaW4gZWxlY3Ryb25pYwpmb3JtYXQgaW4gYWNjb3JkYW5jZSB3aXRoIHRoZSB0ZXJtcyBhbmQgY29uZGl0aW9ucyBvZiB0aGUgRnVsbCBEZXBvc2l0CkxpY2VuY2UgYW5kIHRoZSBVbml2ZXJzaXR5J3MgSW50ZWxsZWN0dWFsIFByb3BlcnR5IEluY2x1ZGluZyAKbnZlbnRpb25zIGFuZCBQYXRlbnRzIFBvbGljeS4KPC9wPjxwPkluIGdyYW50aW5nIHRoZSBsaWNlbmNlIEkgdW5kZXJzdGFuZCB0aGF0Ogo8L3A+PHA+KiBJIGFtIGZyZWUgdG8gcHVibGlzaCB0aGUgV29yayBpbiBpdHMgcHJlc2VudCB2ZXJzaW9uIG9yCmZ1dHVyZSB2ZXJzaW9ucyBlbHNld2hlcmUsIGFuZCBubyBvd25lcnNoaXAgaXMgYXNzdW1lZCBieSAKVGhlIFVuaXZlcnNpdHkgb2YgQXVja2xhbmQgTGlicmFyeSB3aGVuIHN0b3JpbmcgYSBkaWdpdGFsIGNvcHkgb2YgCnRoZSBXb3JrOwoqIElmIGNvcHlyaWdodCBoYXMgYWxyZWFkeSBiZWVuIHRyYW5zZmVycmVkIHRvIGEgcHVibGlzaGVyLApSZXNlYXJjaFNwYWNlIEFkbWluaXN0cmF0b3JzIHdpbGwgb25seSBjb21tdW5pY2F0ZSBvciBtYWtlIGF2YWlsYWJsZQp0aGUgV29yayBpbiBhY2NvcmRhbmNlIHdpdGggdGhlIHB1Ymxpc2hlcidzIGNvcHlyaWdodCBjb25kaXRpb25zOwoqIE9uY2UgdGhlIFdvcmsgaXMgdXBsb2FkZWQgdG8gUmVzZWFyY2hTcGFjZSBhIGNpdGF0aW9uIHdpbGwgCmFsd2F5cyByZW1haW4gdmlzaWJsZSBhbHRob3VnaCBhcyB0aGUgY29weXJpZ2h0IG93bmVyLCBvciB3aXRoIHRoZQpleHByZXNzIGF1dGhvcmlzYXRpb24gb2YgdGhlIGNvcHlyaWdodCBvd25lciwgSSB3aWxsIHJldGFpbiB0aGUgcmlnaHQKdG8gdXBkYXRlIGl0OwoqIFJlc2VhcmNoU3BhY2UgQWRtaW5pc3RyYXRvcnMgbWF5IGtlZXAgbW9yZSB0aGFuIG9uZSBjb3B5IG9mIHRoZQpXb3JrIGZvciBwdXJwb3NlcyBvZiBzZWN1cml0eSwgYmFjay11cCBhbmQgcHJlc2VydmF0aW9uOwoqIEkgbWF5IHJlbW92ZSB0aGUgV29yayBmcm9tIFJlc2VhcmNoU3BhY2UgYW5kIHRoYXQgdGhpcyBwcm9jZXNzIG1heQp0YWtlIHVwIHRvIGZpdmUgd29ya2luZyBkYXlzOwoqIFRoZSBVbml2ZXJzaXR5IG9mIEF1Y2tsYW5kIExpYnJhcnkgbWF5IHJlbW92ZSB0aGUgV29yayBmcm9tIApSZXNlYXJjaFNwYWNlIHdpdGhvdXQgbm90aWNlIGZvciBwcm9mZXNzaW9uYWwsIGxlZ2FsIG9yIGFkbWluaXN0cmF0aXZlCnJlYXNvbnMuPC9wPgo8cD5JIEFncmVlIGFzIGZvbGxvd3M6PC9wPgo8cD4qIEkgaGF2ZSB0aGUgYXV0aG9yaXR5IHRvIG1ha2UgdGhpcyBhZ3JlZW1lbnQgYXMgY29weXJpZ2h0IG93bmVyLCAKb3Igd2l0aCB0aGUgZXhwcmVzcyBhdXRob3Jpc2F0aW9uIG9mIHRoZSBjb3B5cmlnaHQgb3duZXIsIGFuZCBoZXJlYnkKZ2l2ZSBUaGUgVW5pdmVyc2l0eSBvZiBBdWNrbGFuZCBMaWJyYXJ5J3MgUmVzZWFyY2hTcGFjZSBBZG1pbmlzdHJhdG9ycwp0aGUgcmlnaHQgdG8gbWFrZSB0aGUgV29yayBhdmFpbGFibGUgaW4gdGhlIHdheSBkZXNjcmliZWQgYWJvdmUuCiogVGhlIFdvcmsgZG9lcyBub3QgYnJlYWNoIHRoZSBwcml2YWN5IG9mIGFueSB0aGlyZCBwYXJ0eSBvciBjb250YWluCmRlZmFtYXRvcnksIG9mZmVuc2l2ZSBvciB1bmxhd2Z1bCBtYXR0ZXIuCiogQWxsIGNvbnRlbnQgaGFzIGJlZW4gcHJvcGVybHkgYWNrbm93bGVkZ2VkLCBhbmQgZWl0aGVyOgooYSkgdGhlIFdvcmsgZG9lcyBub3QgaW5mcmluZ2UgdGhlIGNvcHlyaWdodCBvZiBhbnkgb3RoZXIgcGVyc29uLCBvcgooYikgSSBoYXZlIG9idGFpbmVkIHdyaXR0ZW4gcGVybWlzc2lvbiB0byB1c2UgYW55IG90aGVyIHBlcnNvbidzIApjb3B5cmlnaHQgbWF0ZXJpYWwgYW5kLCBpZiB0aGUgV29yayBpcyB1bnB1Ymxpc2hlZCwgYXR0YWNoIGNvcGllcyBvZgplYWNoIHBlcm1pc3Npb24uCiogUmVzZWFyY2hTcGFjZSBBZG1pbmlzdHJhdG9ycyBhcmUgdW5kZXIgbm8gb2JsaWdhdGlvbiB0byBkZWZlbmQgb3IKdGFrZSBsZWdhbCBhY3Rpb24gb24gbXkgYmVoYWxmLCBvciBvbiBiZWhhbGYgb2YgYW55IG90aGVyIHJpZ2h0cwpob2xkZXIocykgaWYgdGhlIFdvcmsgYnJlYWNoZXMgaW50ZWxsZWN0dWFsIHByb3BlcnR5IHJpZ2h0cywgb3IgaXMKb3RoZXJ3aXNlIHN1YmplY3QgdG8gbGVnYWwgZGlzcHV0ZS4KKiBJZiB0aGUgV29yayBpcyBiYXNlZCB1cG9uIHdvcmsgdGhhdCBoYXMgYmVlbiBzcG9uc29yZWQgb3IgZnVuZGVkIGJ5CmFuIGVudGl0eSBvdGhlciB0aGFuIFRoZSBVbml2ZXJzaXR5IG9mIEF1Y2tsYW5kLCBJIHJlcHJlc2VudCB0aGF0IEkKaGF2ZSBmdWxmaWxsZWQgYW55IHJpZ2h0IG9mIHJldmlldyBvciBvdGhlciBvYmxpZ2F0aW9uIHJlcXVpcmVkIG9mIG1lCnVuZGVyIHRoZSBjb250cmFjdCBvciBhZ3JlZW1lbnQgd2l0aCB0aGF0IGVudGl0eSBhbmQgdGhhdCB0aGUgdXNlIG9mCnRoZSBXb3JrIGFzIHNldCBvdXQgaW4gdGhpcyBsaWNlbmNlIGRvZXMgbm90IGluZnJpbmdlIHRoZSBpbnRlbGxlY3R1YWwKcHJvcGVydHkgcmlnaHRzIG9mIHRoZSBlbnRpdHkuCiogSSBoYXZlIHJlYWQgYW5kIGFncmVlIHRvIGJlIGJvdW5kIGJ5IHRoZSAgPGEgaHJlZj0iaHR0cDovL3Jlc2VhcmNoc3BhY2UuYXVja2xhbmQuYWMubnovZG9jcy91b2EtZG9jcy9kZXBvc2l0bGljZW5jZWZ1bGwuaHRtIj5GdWxsIERlcG9zaXQgTGljZW5jZTwvYT4KdGVybXMgYW5kIGNvbmRpdGlvbnMuPC9wPgo=
oai:researchspace.auckland.ac.nz:2292/3665
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Lee, S.Y.P
Dinneen, Michael
2009-04-16T23:09:45Z
2009-04-16T23:09:45Z
2001-06
CDMTCS Research Reports CDMTCS-157 (2001)
1178-3540
http://hdl.handle.net/2292/3665
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.
Made available in DSpace on 2009-04-16T23:09:45Z (GMT). No. of bitstreams: 1
157sophia.pdf: 1007741 bytes, checksum: 4b6a38c9c3d71ed36df1aa1e7d85457e (MD5)
Previous issue date: 2001-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Conference Submission Web Server
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
157sophia.pdf
application/pdf
1007741
https://researchspace.auckland.ac.nz/bitstream/2292/3665/1/157sophia.pdf
4b6a38c9c3d71ed36df1aa1e7d85457e
MD5
1
TEXT
157sophia.pdf.txt
157sophia.pdf.txt
text/plain
35216
https://researchspace.auckland.ac.nz/bitstream/2292/3665/2/157sophia.pdf.txt
3ffdf4f058dd8011637f93adf6a6112e
MD5
2
2292/3665
oai:researchspace.auckland.ac.nz:2292/3665
2012-02-03 12:23:17.548
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3747
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
Campeanu, C
Dumitrescu, M
2009-04-16T23:09:48Z
2009-04-16T23:09:48Z
2004-05
CDMTCS Research Reports CDMTCS-240 (2004)
1178-3540
http://hdl.handle.net/2292/3747
How likely is that a randomly given (non-) deterministic finite automaton recognizes no
word? A quick reflection seems to indicate that not too many finite automata accept no word;
but, can this intuition be confirmed?
In this paper we offer a statistical approach which allows us to conclude that for automata,
with a large enough number of states, the probability that a given (non-) deterministic finite
automaton recognizes no word is close to zero. More precisely, we will show, with a high
degree of accuracy (i.e., with precision higher than 99% and level of confidence 0.9973), that for
both deterministic and non-deterministic finite automata: a) the probability that an automaton
recognizes no word tends to zero when the number of states and the number of letters in the
alphabet tend to infinity, b) if the number of states is fixed and rather small, then even if the
number of letters of the alphabet of the automaton tends to infinity, the probability is strictly
positive. The result a) is obtained via a statistical analysis; for b) we use a combinatorial and
statistical analysis.
The present analysis shows that for all practical purposes the fraction of automata recognizing
no words tends to zero when the number of states and the number of letters in the alphabet
grow indefinitely.
In the last section we critically discuss the method and result obtained in this paper. From
a theoretical point of view, the result can motivate the search for “certitude”, that is, a proof
of the fact established here in probabilistic terms. In fact, the method used is much more
important than the result itself. The method is “general” in the sense that it can be applied to
a variety of questions in automata theory, certainly some more difficult than the problem solved
in this note.
Made available in DSpace on 2009-04-16T23:09:48Z (GMT). No. of bitstreams: 1
240cris.pdf: 650900 bytes, checksum: 3ae683a2e7dc2d56981af92cf673cf71 (MD5)
Previous issue date: 2004-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Automata Recognizing No Words: A Statistical Approach
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
240cris.pdf
application/pdf
650900
https://researchspace.auckland.ac.nz/bitstream/2292/3747/1/240cris.pdf
3ae683a2e7dc2d56981af92cf673cf71
MD5
1
TEXT
240cris.pdf.txt
240cris.pdf.txt
text/plain
38448
https://researchspace.auckland.ac.nz/bitstream/2292/3747/2/240cris.pdf.txt
ac344be5f6d660219da356dd62d37883
MD5
2
2292/3747
oai:researchspace.auckland.ac.nz:2292/3747
2012-02-03 12:23:13.111
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3727
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Arulanandham, J.J
Calude, C.S
Dinneen, Michael
2009-04-16T23:09:50Z
2009-04-16T23:09:50Z
2003-06
CDMTCS Research Reports CDMTCS-220 (2003)
1178-3540
http://hdl.handle.net/2292/3727
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.
Made available in DSpace on 2009-04-16T23:09:50Z (GMT). No. of bitstreams: 1
220joshua.pdf: 151615 bytes, checksum: 6276410af2469c0b5003bd4e065cfef6 (MD5)
Previous issue date: 2003-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Fast Natural Algorithm for Searching
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
220joshua.pdf
application/pdf
151615
https://researchspace.auckland.ac.nz/bitstream/2292/3727/1/220joshua.pdf
6276410af2469c0b5003bd4e065cfef6
MD5
1
TEXT
220joshua.pdf.txt
220joshua.pdf.txt
text/plain
22091
https://researchspace.auckland.ac.nz/bitstream/2292/3727/2/220joshua.pdf.txt
bfb8ea3efa8a8c35c25b3a298b19f428
MD5
2
2292/3727
oai:researchspace.auckland.ac.nz:2292/3727
2012-02-03 12:23:17.583
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3573
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Hertling, P
2009-04-16T23:09:52Z
2009-04-16T23:09:52Z
1997-10
CDMTCS Research Reports CDMTCS-064 (1997)
1178-3540
http://hdl.handle.net/2292/3573
Every infinite binary sequence is Turing reducible to a random one. This is
a corollary of a result of Peter Gacs stating that for every co-r.e. closed set with
positive measure of infinite sequences there exists a computable mapping which
maps a subset of the set onto the whole space of infinite sequences. Cristian
Calude asked whether in this result one can replace the positive measure condition by a weaker condition not involving the measure. We show that this is
indeed possible: it is sufficient to demand that the co-r.e. closed set contains a
computably growing Cantor set. Furthermore, in the case of a set with positive
measure we construct a surjective computable map which is more effective than
the map constructed by Gacs.
Made available in DSpace on 2009-04-16T23:09:52Z (GMT). No. of bitstreams: 1
064hertling.pdf: 350536 bytes, checksum: 8582807927750fd66acaf90fcadf716e (MD5)
Previous issue date: 1997-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Surjective Functions on Computably Growing Cantor Sets
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
064hertling.pdf
application/pdf
350536
https://researchspace.auckland.ac.nz/bitstream/2292/3573/1/064hertling.pdf
8582807927750fd66acaf90fcadf716e
MD5
1
TEXT
064hertling.pdf.txt
064hertling.pdf.txt
text/plain
40652
https://researchspace.auckland.ac.nz/bitstream/2292/3573/2/064hertling.pdf.txt
6b9f3e8566836f8532d86a48785d5352
MD5
2
2292/3573
oai:researchspace.auckland.ac.nz:2292/3573
2012-02-03 12:23:16.725
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3768
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
Calude, E
Dinneen, Michael
2009-04-16T23:09:54Z
2009-04-16T23:09:54Z
2005-04
CDMTCS Research Reports CDMTCS-261 (2005)
1178-3540
http://hdl.handle.net/2292/3768
The famous story of the number 1729, the smallest integer which can be expressed
as the sum of two positive cubes in two different ways, motivated the
introduction of Taxicab Numbers. The smallest number expressible as the sum of
two cubes in n different ways is called Taxicab(n). So, Taxicab(2) = 1729. Further
on, Taxicab(5) = 48988659276962496. Computing Taxicab(n) is challenging and
interesting, both from mathematical and programming points of view.
The exact value of Taxicab(6) is not known; in view of the results obtained
by Bernstein [1] and Rathbun [14] it follows that Taxicab(6) is in the interval
[10¹⁸, 24153319581254312065344]. In [5] we proved that with probability greater
than 99%, Taxicab(6) = 24153319581254312065344.
In this note we improve the method used in [5] in two ways: we use (1) a larger,
and (2) a better quality random sampling, namely, a sample of 562,500 quantum
random integers drawn from the above mentioned interval using Quantis, [10]. As a
result, we prove that the above value for Taxicab(6) is true with probability greater
than 99.8%.
Made available in DSpace on 2009-04-16T23:09:54Z (GMT). No. of bitstreams: 1
261cris.pdf: 479185 bytes, checksum: cf0087aa2e10b331f0eba3b5b0f4074b (MD5)
Previous issue date: 2005-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
What is the Value of Taxicab(6)? An Update
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
261cris.pdf
application/pdf
479185
https://researchspace.auckland.ac.nz/bitstream/2292/3768/1/261cris.pdf
cf0087aa2e10b331f0eba3b5b0f4074b
MD5
1
TEXT
261cris.pdf.txt
261cris.pdf.txt
text/plain
12871
https://researchspace.auckland.ac.nz/bitstream/2292/3768/2/261cris.pdf.txt
890a741527b39bb448a7f273de90fa4b
MD5
2
2292/3768
oai:researchspace.auckland.ac.nz:2292/3768
2012-02-03 12:23:13.081
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3627
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Dinneen, Michael
Xiong, Liu
2009-04-16T23:09:55Z
2009-04-16T23:09:55Z
2000-01
CDMTCS Research Reports CDMTCS-118 (2000)
1178-3540
http://hdl.handle.net/2292/3627
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.
Made available in DSpace on 2009-04-16T23:09:55Z (GMT). No. of bitstreams: 1
118vc6.pdf: 411511 bytes, checksum: 186cfe3610980f29820ee7e28f8fd6da (MD5)
Previous issue date: 2000-01
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
The Minor-Order Obstructions for The Graphs of Vertex Cover Six
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
118vc6.pdf
application/pdf
411511
https://researchspace.auckland.ac.nz/bitstream/2292/3627/1/118vc6.pdf
186cfe3610980f29820ee7e28f8fd6da
MD5
1
TEXT
118vc6.pdf.txt
118vc6.pdf.txt
text/plain
48214
https://researchspace.auckland.ac.nz/bitstream/2292/3627/2/118vc6.pdf.txt
fa6004c4a5f08c400d03963cedca88a2
MD5
2
2292/3627
oai:researchspace.auckland.ac.nz:2292/3627
2012-02-03 12:23:17.021
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3695
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Becher, V
Chaitin, G.J
2009-04-16T23:09:57Z
2009-04-16T23:09:57Z
2002-05
CDMTCS Research Reports CDMTCS-187 (2002)
1178-3540
http://hdl.handle.net/2292/3695
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.
Made available in DSpace on 2009-04-16T23:09:57Z (GMT). No. of bitstreams: 1
187vero.pdf: 192546 bytes, checksum: 2e57a6dfe14925f396db957499b5f3fa (MD5)
Previous issue date: 2002-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Another Example of Higher Order Randomness
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
187vero.pdf
application/pdf
192546
https://researchspace.auckland.ac.nz/bitstream/2292/3695/1/187vero.pdf
2e57a6dfe14925f396db957499b5f3fa
MD5
1
TEXT
187vero.pdf.txt
187vero.pdf.txt
text/plain
37735
https://researchspace.auckland.ac.nz/bitstream/2292/3695/2/187vero.pdf.txt
c8db933707720d96b67356b73c862d0d
MD5
2
2292/3695
oai:researchspace.auckland.ac.nz:2292/3695
2012-02-03 12:23:13.097
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3624
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Kapoulas, G
2009-04-16T23:09:59Z
2009-04-16T23:09:59Z
1999-11
CDMTCS Research Reports CDMTCS-115 (1999)
1178-3540
http://hdl.handle.net/2292/3624
In the present work the notion of the computable (primitive recursive,
polynomially time computable) p-adic number is introduced and studied. Basic properties
of these numbers and the set of indices representing them are established and it
is proved that the above defined fields are p-adically closed. Using the notion of a notation
system introduced by Y. Moschovakis an abstract characterization of the indices
representing the field of computable p-adic numbers is established.
Made available in DSpace on 2009-04-16T23:09:59Z (GMT). No. of bitstreams: 1
115george.pdf: 235100 bytes, checksum: f11da230ed90eeadc4329690218841dd (MD5)
Previous issue date: 1999-11
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Computable $p$-adic Numbers
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
115george.pdf
application/pdf
235100
https://researchspace.auckland.ac.nz/bitstream/2292/3624/1/115george.pdf
f11da230ed90eeadc4329690218841dd
MD5
1
TEXT
115george.pdf.txt
115george.pdf.txt
text/plain
61049
https://researchspace.auckland.ac.nz/bitstream/2292/3624/2/115george.pdf.txt
9ff23e4ade9dd429bbb4f65b34585637
MD5
2
2292/3624
oai:researchspace.auckland.ac.nz:2292/3624
2012-02-03 12:23:13.525
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3771
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Staiger, L
2009-04-16T23:10:00Z
2009-04-16T23:10:00Z
2005-04
CDMTCS Research Reports CDMTCS-264 (2005)
1178-3540
http://hdl.handle.net/2292/3771
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.
Made available in DSpace on 2009-04-16T23:10:00Z (GMT). No. of bitstreams: 1
264ludwig.pdf: 254382 bytes, checksum: 76a7904d378935e4cd3402ca61b5fd43 (MD5)
Previous issue date: 2005-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Infinite Iterated Function Systems in Cantor Space and the Hausdorff Measure of omega-power Languages
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
264ludwig.pdf
application/pdf
254382
https://researchspace.auckland.ac.nz/bitstream/2292/3771/1/264ludwig.pdf
76a7904d378935e4cd3402ca61b5fd43
MD5
1
TEXT
264ludwig.pdf.txt
264ludwig.pdf.txt
text/plain
38126
https://researchspace.auckland.ac.nz/bitstream/2292/3771/2/264ludwig.pdf.txt
3b47128f64ac7aad2b989f4f911e5f30
MD5
2
2292/3771
oai:researchspace.auckland.ac.nz:2292/3771
2012-02-03 12:23:15.351
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3774
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Titchener, M.R
Speidel, U
Yang, J
2009-04-16T23:10:02Z
2009-04-16T23:10:02Z
2005-05
CDMTCS Research Reports CDMTCS-267 (2005)
1178-3540
http://hdl.handle.net/2292/3774
This report compares a variety of computable information measures for finite strings. These include
Shannon’s n-block entropy, the three best known versions of the Lempel-Ziv production complexity
(LZ-76, LZ-77, and LZ-78), and the lesser known T-entropy. We apply these measures to strings of
known entropy, each derived from the logistic map. Pesin’s identity allows us to deduce corresponding
Shannon entropies (Kolmogorov-Sinai entropies) for the sample strings, without resorting to probabilistic
methods.
Made available in DSpace on 2009-04-16T23:10:02Z (GMT). No. of bitstreams: 1
267titchener.pdf: 530784 bytes, checksum: a5ddf3fdce5f1de400c3ef8f8b00c7fe (MD5)
Previous issue date: 2005-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Comparison of Practical Information Measures
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
267titchener.pdf
application/pdf
530784
https://researchspace.auckland.ac.nz/bitstream/2292/3774/1/267titchener.pdf
a5ddf3fdce5f1de400c3ef8f8b00c7fe
MD5
1
TEXT
267titchener.pdf.txt
267titchener.pdf.txt
text/plain
19687
https://researchspace.auckland.ac.nz/bitstream/2292/3774/2/267titchener.pdf.txt
ad886ad5197e7a92bbd7b5b4b6c87c06
MD5
2
2292/3774
oai:researchspace.auckland.ac.nz:2292/3774
2012-02-03 12:23:13.198
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3796
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
Firror, G
Mansour, T
Wilson, Mark
2009-04-16T23:10:04Z
2009-04-16T23:10:04Z
2006-10
CDMTCS Research Reports CDMTCS-289 (2006)
1178-3540
http://hdl.handle.net/2292/3796
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.
Made available in DSpace on 2009-04-16T23:10:04Z (GMT). No. of bitstreams: 1
289wilson.pdf: 570072 bytes, checksum: 5b75658d6c0442e48db1bbbe3577362f (MD5)
Previous issue date: 2006-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Longest Alternating Subsequences in Pattern-Restricted Permutations
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
289wilson.pdf
application/pdf
570072
https://researchspace.auckland.ac.nz/bitstream/2292/3796/1/289wilson.pdf
5b75658d6c0442e48db1bbbe3577362f
MD5
1
TEXT
289wilson.pdf.txt
289wilson.pdf.txt
text/plain
383
https://researchspace.auckland.ac.nz/bitstream/2292/3796/2/289wilson.pdf.txt
e16376c730275dcc7d67c8d8d7f4f3aa
MD5
2
2292/3796
oai:researchspace.auckland.ac.nz:2292/3796
2012-02-03 12:23:18.63
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3793
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Speidel, U
2009-04-16T23:10:05Z
2009-04-16T23:10:05Z
2006-10
CDMTCS Research Reports CDMTCS-286 (2006)
1178-3540
http://hdl.handle.net/2292/3793
This paper describes the derivation of the T-complexity and T-in-
formation theory from the decomposition of finite strings, based on the
duality of strings and variable-length T-codes. It further outlines its similarity to the string parsing algorithm by Lempel and Ziv. In its first
version [15], it was intended as a summary of work published mainly by
Titchener and Nicolescu. Apart from minor corrections, the present extended version incorporates feedback from previous readers and presents
new results obtained since.
Made available in DSpace on 2009-04-16T23:10:05Z (GMT). No. of bitstreams: 1
286ulrich.pdf: 140932 bytes, checksum: c2cfbd1ac38f9d8b707e8e186dfacae2 (MD5)
Previous issue date: 2006-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
T-Complexity and T-Information Theory--an Executive Summary, 2nd revised version
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
286ulrich.pdf
application/pdf
140932
https://researchspace.auckland.ac.nz/bitstream/2292/3793/1/286ulrich.pdf
c2cfbd1ac38f9d8b707e8e186dfacae2
MD5
1
TEXT
286ulrich.pdf.txt
286ulrich.pdf.txt
text/plain
25140
https://researchspace.auckland.ac.nz/bitstream/2292/3793/2/286ulrich.pdf.txt
c924f3e8bb6a2a42a9f01947198cee41
MD5
2
2292/3793
oai:researchspace.auckland.ac.nz:2292/3793
2012-02-03 12:23:16.781
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3574
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Hertling, P
2009-04-16T23:10:07Z
2009-04-16T23:10:07Z
1997-10
CDMTCS Research Reports CDMTCS-065 (1997)
1178-3540
http://hdl.handle.net/2292/3574
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.
Made available in DSpace on 2009-04-16T23:10:07Z (GMT). No. of bitstreams: 1
065hertling.pdf: 270542 bytes, checksum: 07f747b088f21b8a5b14a88c55d3dee3 (MD5)
Previous issue date: 1997-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Embedding Cellular Automata into Reversible Ones
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
065hertling.pdf
application/pdf
270542
https://researchspace.auckland.ac.nz/bitstream/2292/3574/1/065hertling.pdf
07f747b088f21b8a5b14a88c55d3dee3
MD5
1
TEXT
065hertling.pdf.txt
065hertling.pdf.txt
text/plain
37870
https://researchspace.auckland.ac.nz/bitstream/2292/3574/2/065hertling.pdf.txt
fe162bd60eb830a9d4e7931ea1d5596e
MD5
2
2292/3574
oai:researchspace.auckland.ac.nz:2292/3574
2012-02-03 12:23:14.155
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3867
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Svozil, K
2009-04-16T23:10:09Z
2009-04-16T23:10:09Z
2009-04
CDMTCS Research Reports CDMTCS-360 (2009)
1178-3540
http://hdl.handle.net/2292/3867
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.
Made available in DSpace on 2009-04-16T23:10:09Z (GMT). No. of bitstreams: 1
361karl.pdf: 296461 bytes, checksum: 2d515dd7502ce3de17b9f2799dec1340 (MD5)
Previous issue date: 2009-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
On the Brightness of the Thomson lamp. A Prolegomenon to Quantum Recursion Theory
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
361karl.pdf
application/pdf
296461
https://researchspace.auckland.ac.nz/bitstream/2292/3867/1/361karl.pdf
2d515dd7502ce3de17b9f2799dec1340
MD5
1
TEXT
361karl.pdf.txt
361karl.pdf.txt
text/plain
32558
https://researchspace.auckland.ac.nz/bitstream/2292/3867/2/361karl.pdf.txt
d22f9f7bd8e0435ed73b39880cd86fbd
MD5
2
2292/3867
oai:researchspace.auckland.ac.nz:2292/3867
2012-02-03 12:23:14.978
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3792
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
2009-04-16T23:10:10Z
2009-04-16T23:10:10Z
2006-08
CDMTCS Research Reports CDMTCS-285 (2006)
1178-3540
http://hdl.handle.net/2292/3792
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.
Made available in DSpace on 2009-04-16T23:10:10Z (GMT). No. of bitstreams: 1
285cris.pdf: 231689 bytes, checksum: 2c24601fdb08b7348cf087e12d559fae (MD5)
Previous issue date: 2006-08
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
De-Quantising the Solution of Deutsch's Prolem
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
285cris.pdf
application/pdf
231689
https://researchspace.auckland.ac.nz/bitstream/2292/3792/1/285cris.pdf
2c24601fdb08b7348cf087e12d559fae
MD5
1
TEXT
285cris.pdf.txt
285cris.pdf.txt
text/plain
12401
https://researchspace.auckland.ac.nz/bitstream/2292/3792/2/285cris.pdf.txt
ddcf7a27656a688b089fd4f5aa1dd447
MD5
2
2292/3792
oai:researchspace.auckland.ac.nz:2292/3792
2012-02-03 12:23:15.231
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3693
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Khoussainov, B
Rubin, S
2009-04-16T23:10:12Z
2009-04-16T23:10:12Z
2002-05
CDMTCS Research Reports CDMTCS-185 (2002)
1178-3540
http://hdl.handle.net/2292/3693
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
Made available in DSpace on 2009-04-16T23:10:12Z (GMT). No. of bitstreams: 1
185sasha.pdf: 190201 bytes, checksum: 96b584d0c9cdee34b4d5561148fbb8a3 (MD5)
Previous issue date: 2002-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Some Thoughts On Automatic Structures
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
185sasha.pdf
application/pdf
190201
https://researchspace.auckland.ac.nz/bitstream/2292/3693/1/185sasha.pdf
96b584d0c9cdee34b4d5561148fbb8a3
MD5
1
TEXT
185sasha.pdf.txt
185sasha.pdf.txt
text/plain
37735
https://researchspace.auckland.ac.nz/bitstream/2292/3693/2/185sasha.pdf.txt
d49637c68daf3ea2fadf3d1bf4c2aad1
MD5
2
2292/3693
oai:researchspace.auckland.ac.nz:2292/3693
2012-02-03 12:23:17.848
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3770
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Pemantle, R
Wilson, Mark
2009-04-16T23:10:13Z
2009-04-16T23:10:13Z
2005-04
CDMTCS Research Reports CDMTCS-263 (2005)
1178-3540
http://hdl.handle.net/2292/3770
The purpose of this paper is to review recent developments in the asymptotics of
multivariate generating functions, and to give an exposition of these that is accessible
and centered around applications. We begin, however, with a brief review of univariate
generating functions and of previous results on multivariate generating functions.
Made available in DSpace on 2009-04-16T23:10:13Z (GMT). No. of bitstreams: 1
263mcwrap.pdf: 679103 bytes, checksum: 37b56f375dfab459ad49e6b780f9d96f (MD5)
Previous issue date: 2005-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Twenty Combinatorial Examples of Asymptotics Derived From Multivariate Generating Functions
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
263mcwrap.pdf
application/pdf
679103
https://researchspace.auckland.ac.nz/bitstream/2292/3770/1/263mcwrap.pdf
37b56f375dfab459ad49e6b780f9d96f
MD5
1
TEXT
263mcwrap.pdf.txt
263mcwrap.pdf.txt
text/plain
156598
https://researchspace.auckland.ac.nz/bitstream/2292/3770/2/263mcwrap.pdf.txt
ef92838b2049d6ba3dc268c105e8438a
MD5
2
2292/3770
oai:researchspace.auckland.ac.nz:2292/3770
2012-02-03 12:23:13.264
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3667
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Bridges, D.S
Vita, L.S
2009-04-16T23:10:15Z
2009-04-16T23:10:15Z
2001-08
CDMTCS Research Reports CDMTCS-159 (2001)
1178-3540
http://hdl.handle.net/2292/3667
An axiomatic constructive development of the theory of nearness and apartness
of a point and a set is introduced as a setting for topology.
Made available in DSpace on 2009-04-16T23:10:15Z (GMT). No. of bitstreams: 1
159Bridges.pdf: 175992 bytes, checksum: 7f8723fcb52e4f2ba4bf8c0d81add774 (MD5)
Previous issue date: 2001-08
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Constructive Theory of Point-Set Nearness
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
159Bridges.pdf
application/pdf
175992
https://researchspace.auckland.ac.nz/bitstream/2292/3667/1/159Bridges.pdf
7f8723fcb52e4f2ba4bf8c0d81add774
MD5
1
TEXT
159Bridges.pdf.txt
159Bridges.pdf.txt
text/plain
34294
https://researchspace.auckland.ac.nz/bitstream/2292/3667/2/159Bridges.pdf.txt
de17dc14499abc1185b7ff4d812aafd6
MD5
2
2292/3667
oai:researchspace.auckland.ac.nz:2292/3667
2012-02-03 12:23:13.759
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3749
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Juarna, A
Vajnovszki, V
2009-04-16T23:10:16Z
2009-04-16T23:10:16Z
2004-07
CDMTCS Research Reports CDMTCS-242 (2004)
1178-3540
http://hdl.handle.net/2292/3749
[no abstract available]
Made available in DSpace on 2009-04-16T23:10:16Z (GMT). No. of bitstreams: 1
242vincent.pdf: 216807 bytes, checksum: ec8875ea5b2d13430561a8fd18a2b6ab (MD5)
Previous issue date: 2004-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Fast Generation of Fibonacci Permutations
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
242vincent.pdf
application/pdf
216807
https://researchspace.auckland.ac.nz/bitstream/2292/3749/1/242vincent.pdf
ec8875ea5b2d13430561a8fd18a2b6ab
MD5
1
TEXT
242vincent.pdf.txt
242vincent.pdf.txt
text/plain
17711
https://researchspace.auckland.ac.nz/bitstream/2292/3749/2/242vincent.pdf.txt
4027874738f9453ae23fc1e95e06e990
MD5
2
2292/3749
oai:researchspace.auckland.ac.nz:2292/3749
2012-02-03 12:23:17.286
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3593
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
Calude, C.S
Dinneen, Michael
2009-04-16T23:10:18Z
2009-04-16T23:10:18Z
1998-05
CDMTCS Research Reports CDMTCS-084 (1998)
1178-3540
http://hdl.handle.net/2292/3593
Is there any limit to discrete computation, and more generally, to scientific knowledge? This is one of the problems studied by the Centre for Discrete Mathematics and
Theoretical Computer Science of the University of Auckland.
Made available in DSpace on 2009-04-16T23:10:18Z (GMT). No. of bitstreams: 1
084turing.pdf: 144362 bytes, checksum: 6958a47bc557c371a9b3a5c7233c7941 (MD5)
Previous issue date: 1998-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Breaking the Turing Barrier
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
084turing.pdf
application/pdf
144362
https://researchspace.auckland.ac.nz/bitstream/2292/3593/1/084turing.pdf
6958a47bc557c371a9b3a5c7233c7941
MD5
1
TEXT
084turing.pdf.txt
084turing.pdf.txt
text/plain
8767
https://researchspace.auckland.ac.nz/bitstream/2292/3593/2/084turing.pdf.txt
a97ec941ae54bf85244cdd72a59f3b6d
MD5
2
2292/3593
oai:researchspace.auckland.ac.nz:2292/3593
2012-02-03 12:23:18.519
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3600
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Dinneen, M.J
2009-04-16T23:10:20Z
2009-04-16T23:10:20Z
1998-10
CDMTCS Research Reports CDMTCS-091 (1998)
1178-3540
http://hdl.handle.net/2292/3600
[no abstract available]
Made available in DSpace on 2009-04-16T23:10:20Z (GMT). No. of bitstreams: 1
091mjd.pdf: 147780 bytes, checksum: c43272a04b46ea6299a9856342e90e63 (MD5)
Previous issue date: 1998-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Abstracts of the 2nd Japan - New Zealand Workshop on Logic in Computer Science
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
091mjd.pdf
application/pdf
147780
https://researchspace.auckland.ac.nz/bitstream/2292/3600/1/091mjd.pdf
c43272a04b46ea6299a9856342e90e63
MD5
1
TEXT
091mjd.pdf.txt
091mjd.pdf.txt
text/plain
5824
https://researchspace.auckland.ac.nz/bitstream/2292/3600/2/091mjd.pdf.txt
57532781342f3ac0ae7fc677687b8103
MD5
2
2292/3600
oai:researchspace.auckland.ac.nz:2292/3600
2012-02-03 12:23:17.909
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3791
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Calude, C.S
Stay, M.A
2009-04-16T23:10:21Z
2009-04-16T23:10:21Z
2006-08
CDMTCS Research Reports CDMTCS-284 (2006)
1178-3540
http://hdl.handle.net/2292/3791
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.
Made available in DSpace on 2009-04-16T23:10:21Z (GMT). No. of bitstreams: 1
284cris.pdf: 600722 bytes, checksum: e0753101497691211b10c2f3de5a49d8 (MD5)
Previous issue date: 2006-08
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Most Short Programs Halt Quickly or Never Halt
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
284cris.pdf
application/pdf
600722
https://researchspace.auckland.ac.nz/bitstream/2292/3791/1/284cris.pdf
e0753101497691211b10c2f3de5a49d8
MD5
1
TEXT
284cris.pdf.txt
284cris.pdf.txt
text/plain
35521
https://researchspace.auckland.ac.nz/bitstream/2292/3791/2/284cris.pdf.txt
f676fda4057eff7aba1ced64e1396a5b
MD5
2
2292/3791
oai:researchspace.auckland.ac.nz:2292/3791
2012-02-03 12:23:17.035
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3772
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Stay, M
2009-04-16T23:10:23Z
2009-04-16T23:10:23Z
2005-05
CDMTCS Research Reports CDMTCS-265 (2005)
1178-3540
http://hdl.handle.net/2292/3772
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.
Made available in DSpace on 2009-04-16T23:10:23Z (GMT). No. of bitstreams: 1
265stay.pdf: 447308 bytes, checksum: dc09991619ab76108043fc5f896c879a (MD5)
Previous issue date: 2005-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Very Simple Chaitin Machines for Concrete AIT
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
265stay.pdf
application/pdf
447308
https://researchspace.auckland.ac.nz/bitstream/2292/3772/1/265stay.pdf
dc09991619ab76108043fc5f896c879a
MD5
1
TEXT
265stay.pdf.txt
265stay.pdf.txt
text/plain
38252
https://researchspace.auckland.ac.nz/bitstream/2292/3772/2/265stay.pdf.txt
50d6dfb816f8eef0b9568ae28736ada9
MD5
2
2292/3772
oai:researchspace.auckland.ac.nz:2292/3772
2012-02-03 12:23:17.972
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3644
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Downey, R.G
LaForte, G.L
2009-04-16T23:10:24Z
2009-04-16T23:10:24Z
2000-05
CDMTCS Research Reports CDMTCS-135 (2000)
1178-3540
http://hdl.handle.net/2292/3644
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.
Made available in DSpace on 2009-04-16T23:10:24Z (GMT). No. of bitstreams: 1
135rod.pdf: 288575 bytes, checksum: 19400bc1005ba1a460c9631df7d21167 (MD5)
Previous issue date: 2000-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Presentations of Computably Enumerable Reals
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
135rod.pdf
application/pdf
288575
https://researchspace.auckland.ac.nz/bitstream/2292/3644/1/135rod.pdf
19400bc1005ba1a460c9631df7d21167
MD5
1
TEXT
135rod.pdf.txt
135rod.pdf.txt
text/plain
77623
https://researchspace.auckland.ac.nz/bitstream/2292/3644/2/135rod.pdf.txt
cdd13e14cc2d93c1fe2d42fc6670f332
MD5
2
2292/3644
oai:researchspace.auckland.ac.nz:2292/3644
2012-02-03 12:23:16.277
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3521
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Antoniou, I
Pavlov, B
Yafyasov, A
2009-04-16T23:10:25Z
2009-04-16T23:10:25Z
1996-04
CDMTCS Research Reports CDMTCS-012 (1996)
1178-3540
http://hdl.handle.net/2292/3521
[no abstract available]
Made available in DSpace on 2009-04-16T23:10:25Z (GMT). No. of bitstreams: 1
012borisp.pdf: 543323 bytes, checksum: 1934aeb6b412f9c5715eb2925227c735 (MD5)
Previous issue date: 1996-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Quantum Electronic Devices Based on Metal-Dielectric Transition in Low-Dimensional Quantum Structures
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
012borisp.pdf
application/pdf
543323
https://researchspace.auckland.ac.nz/bitstream/2292/3521/1/012borisp.pdf
1934aeb6b412f9c5715eb2925227c735
MD5
1
TEXT
012borisp.pdf.txt
012borisp.pdf.txt
text/plain
35137
https://researchspace.auckland.ac.nz/bitstream/2292/3521/2/012borisp.pdf.txt
170604626ec330632f42377f8c6f172d
MD5
2
2292/3521
oai:researchspace.auckland.ac.nz:2292/3521
2012-02-03 12:23:14.708
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3645
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Svozil, K
2009-04-16T23:10:27Z
2009-04-16T23:10:27Z
2000-05
CDMTCS Research Reports CDMTCS-136 (2000)
1178-3540
http://hdl.handle.net/2292/3645
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.
Made available in DSpace on 2009-04-16T23:10:27Z (GMT). No. of bitstreams: 1
136karl.pdf: 393061 bytes, checksum: da6571fb28b54eefe350a6abb7e8c493 (MD5)
Previous issue date: 2000-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Quantum Interfaces
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
136karl.pdf
application/pdf
393061
https://researchspace.auckland.ac.nz/bitstream/2292/3645/1/136karl.pdf
da6571fb28b54eefe350a6abb7e8c493
MD5
1
TEXT
136karl.pdf.txt
136karl.pdf.txt
text/plain
36659
https://researchspace.auckland.ac.nz/bitstream/2292/3645/2/136karl.pdf.txt
8cfdb05f35a992c51890442e1cb0a32e
MD5
2
2292/3645
oai:researchspace.auckland.ac.nz:2292/3645
2012-02-03 12:23:15.45
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3522
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C
Grozea, C
2009-04-16T23:10:28Z
2009-04-16T23:10:28Z
1996-04
CDMTCS Research Reports CDMTCS-013 (1996)
1178-3540
http://hdl.handle.net/2292/3522
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.
Made available in DSpace on 2009-04-16T23:10:28Z (GMT). No. of bitstreams: 1
013cris2.pdf: 490121 bytes, checksum: 61f0434b9401d821b9abc92dc02e6f25 (MD5)
Previous issue date: 1996-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Kraft-Chaitin Inequality Revisited
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
013cris2.pdf
application/pdf
490121
https://researchspace.auckland.ac.nz/bitstream/2292/3522/1/013cris2.pdf
61f0434b9401d821b9abc92dc02e6f25
MD5
1
TEXT
013cris2.pdf.txt
013cris2.pdf.txt
text/plain
9660
https://researchspace.auckland.ac.nz/bitstream/2292/3522/2/013cris2.pdf.txt
431114d91c22e341b627b9a360297145
MD5
2
2292/3522
oai:researchspace.auckland.ac.nz:2292/3522
2012-02-03 12:23:15.699
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3795
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
Lladser, M.E
Potocnik, P
Siran, J
Siagiova, J
Wilson, M.C
2009-04-16T23:10:30Z
2009-04-16T23:10:30Z
2006-10
CDMTCS Research Reports CDMTCS-288 (2006)
1178-3540
http://hdl.handle.net/2292/3795
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.
Made available in DSpace on 2009-04-16T23:10:30Z (GMT). No. of bitstreams: 1
288wilson.pdf: 227161 bytes, checksum: 59398fda4366ef7352d5cb1d4020100b (MD5)
Previous issue date: 2006-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
The Diameter of Random Cayley Digraphs of Given Degree
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
288wilson.pdf
application/pdf
227161
https://researchspace.auckland.ac.nz/bitstream/2292/3795/1/288wilson.pdf
59398fda4366ef7352d5cb1d4020100b
MD5
1
TEXT
288wilson.pdf.txt
288wilson.pdf.txt
text/plain
37938
https://researchspace.auckland.ac.nz/bitstream/2292/3795/2/288wilson.pdf.txt
96388ef0427d81492b46b1a2040459ec
MD5
2
2292/3795
oai:researchspace.auckland.ac.nz:2292/3795
2012-02-03 12:23:19.151
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3591
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Calude, C.S
Dinneen, Michael
2009-04-16T23:10:31Z
2009-04-16T23:10:31Z
1998-05
CDMTCS Research Reports CDMTCS-082 (1998)
1178-3540
http://hdl.handle.net/2292/3591
[no abstract available]
Made available in DSpace on 2009-04-16T23:10:31Z (GMT). No. of bitstreams: 1
082nznews.pdf: 267895 bytes, checksum: 803c606b99f72eb5152a3d4830c5bb1f (MD5)
Previous issue date: 1998-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
News from New Zealand / Group-Theoretic Methods for Designing Networks
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
082nznews.pdf
application/pdf
267895
https://researchspace.auckland.ac.nz/bitstream/2292/3591/1/082nznews.pdf
803c606b99f72eb5152a3d4830c5bb1f
MD5
1
TEXT
082nznews.pdf.txt
082nznews.pdf.txt
text/plain
14982
https://researchspace.auckland.ac.nz/bitstream/2292/3591/2/082nznews.pdf.txt
d46337c6dd228dd90fdd362e12a56995
MD5
2
2292/3591
oai:researchspace.auckland.ac.nz:2292/3591
2012-02-03 12:23:14.609
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3789
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Chaitin, G.J
2009-04-16T23:10:33Z
2009-04-16T23:10:33Z
2006-07
CDMTCS Research Reports CDMTCS-282 (2006)
1178-3540
http://hdl.handle.net/2292/3789
It would be nice to have a mathematical understanding of basic biological concepts
and to be able to prove that life must evolve in very general circumstances.
At present we are far from being able to do this. But I’ll discuss some partial steps
in this direction plus what I regard as a possible future line of attack.
Made available in DSpace on 2009-04-16T23:10:33Z (GMT). No. of bitstreams: 1
282greg.pdf: 139034 bytes, checksum: bfcd59a0f1139c522444cdf5fcd60cae (MD5)
Previous issue date: 2006-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Speculations on Biology, Information and Complexity
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
282greg.pdf
application/pdf
139034
https://researchspace.auckland.ac.nz/bitstream/2292/3789/1/282greg.pdf
bfcd59a0f1139c522444cdf5fcd60cae
MD5
1
TEXT
282greg.pdf.txt
282greg.pdf.txt
text/plain
17868
https://researchspace.auckland.ac.nz/bitstream/2292/3789/2/282greg.pdf.txt
a8d7bca66ae009e2b1fdfe67c9fe2aa5
MD5
2
2292/3789
oai:researchspace.auckland.ac.nz:2292/3789
2012-02-03 12:23:14.032
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3773
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
Eimann, R
Speidel, U
Brownlee, N
Yang, J
2009-04-16T23:10:35Z
2009-04-16T23:10:35Z
2005-05
CDMTCS Research Reports CDMTCS-266 (2005)
1178-3540
http://hdl.handle.net/2292/3773
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.
Made available in DSpace on 2009-04-16T23:10:35Z (GMT). No. of bitstreams: 1
266eimann.pdf: 439600 bytes, checksum: 9c0cd4b31d35e23f94876c342ac534fa (MD5)
Previous issue date: 2005-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Network Event Detection with T-Entropy
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
266eimann.pdf
application/pdf
439600
https://researchspace.auckland.ac.nz/bitstream/2292/3773/1/266eimann.pdf
9c0cd4b31d35e23f94876c342ac534fa
MD5
1
TEXT
266eimann.pdf.txt
266eimann.pdf.txt
text/plain
25562
https://researchspace.auckland.ac.nz/bitstream/2292/3773/2/266eimann.pdf.txt
46249bfb0879d754d889222c53a8c414
MD5
2
2292/3773
oai:researchspace.auckland.ac.nz:2292/3773
2012-02-03 12:23:18.648
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3642
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Kearse, M.D
Gibbons, P.B
2009-04-16T23:10:36Z
2009-04-16T23:10:36Z
2000-05
CDMTCS Research Reports CDMTCS-133 (2000)
1178-3540
http://hdl.handle.net/2292/3642
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.
Made available in DSpace on 2009-04-16T23:10:36Z (GMT). No. of bitstreams: 1
133chess.pdf: 255369 bytes, checksum: eb6387b5930203576dc0471d924e8176 (MD5)
Previous issue date: 2000-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Computational Methods and New Results for Chessboard Problems
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
133chess.pdf
application/pdf
255369
https://researchspace.auckland.ac.nz/bitstream/2292/3642/1/133chess.pdf
eb6387b5930203576dc0471d924e8176
MD5
1
TEXT
133chess.pdf.txt
133chess.pdf.txt
text/plain
60741
https://researchspace.auckland.ac.nz/bitstream/2292/3642/2/133chess.pdf.txt
683ce27033e5f72665bbc163363b8332
MD5
2
2292/3642
oai:researchspace.auckland.ac.nz:2292/3642
2012-02-03 12:23:15.941
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3607
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Paun, G
2009-04-16T23:10:38Z
2009-04-16T23:10:38Z
1999-03
CDMTCS Research Reports CDMTCS-098 (1999)
1178-3540
http://hdl.handle.net/2292/3607
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.
Made available in DSpace on 2009-04-16T23:10:38Z (GMT). No. of bitstreams: 1
098deltatau.pdf: 219102 bytes, checksum: a360a154e8d5ae7164ca6a276349fa91 (MD5)
Previous issue date: 1999-03
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Computing with Membranes: A Variant
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
098deltatau.pdf
application/pdf
219102
https://researchspace.auckland.ac.nz/bitstream/2292/3607/1/098deltatau.pdf
a360a154e8d5ae7164ca6a276349fa91
MD5
1
TEXT
098deltatau.pdf.txt
098deltatau.pdf.txt
text/plain
33912
https://researchspace.auckland.ac.nz/bitstream/2292/3607/2/098deltatau.pdf.txt
92de86345263e4b1385631b31a1b7db9
MD5
2
2292/3607
oai:researchspace.auckland.ac.nz:2292/3607
2012-02-03 12:23:16.876
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3592
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
Calude, E
Stefanescu, C
2009-04-16T23:10:39Z
2009-04-16T23:10:39Z
1998-05
CDMTCS Research Reports CDMTCS-083 (1998)
1178-3540
http://hdl.handle.net/2292/3592
In this paper we extend (and study) two computational complementary principles from Moore to Mealy automata which are finite machines possessing better “quantum-like” features. We conjecture that automata which are reversible according to Svozil do not satisfy any of these computational complementarity principles. This result is consistent with the embeddability of irreversible computations into reversible ones (via Bennett’s method, for example). Mathematica experiments confirmed this hypothesis.
Made available in DSpace on 2009-04-16T23:10:39Z (GMT). No. of bitstreams: 1
083cec.pdf: 360555 bytes, checksum: 7cb8524813037cd12c09d5afd2c5973a (MD5)
Previous issue date: 1998-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Computational Complementarity for Mealy Automata
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
083cec.pdf
application/pdf
360555
https://researchspace.auckland.ac.nz/bitstream/2292/3592/1/083cec.pdf
7cb8524813037cd12c09d5afd2c5973a
MD5
1
TEXT
083cec.pdf.txt
083cec.pdf.txt
text/plain
27157
https://researchspace.auckland.ac.nz/bitstream/2292/3592/2/083cec.pdf.txt
3be89e04c64e74d770683ac1c39bc3f1
MD5
2
2292/3592
oai:researchspace.auckland.ac.nz:2292/3592
2012-02-03 12:23:15.196
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3575
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Cazanescu, V.E
2009-04-16T23:10:41Z
2009-04-16T23:10:41Z
1997-11
CDMTCS Research Reports CDMTCS-066 (1997)
1178-3540
http://hdl.handle.net/2292/3575
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.
Made available in DSpace on 2009-04-16T23:10:41Z (GMT). No. of bitstreams: 1
066virgil.pdf: 514602 bytes, checksum: 27014b4ed8dd3096cc177be656f2fd16 (MD5)
Previous issue date: 1997-11
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Feedback for Relations
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
066virgil.pdf
application/pdf
514602
https://researchspace.auckland.ac.nz/bitstream/2292/3575/1/066virgil.pdf
27014b4ed8dd3096cc177be656f2fd16
MD5
1
TEXT
066virgil.pdf.txt
066virgil.pdf.txt
text/plain
11527
https://researchspace.auckland.ac.nz/bitstream/2292/3575/2/066virgil.pdf.txt
9705e8821460bc087538a26b46411d2c
MD5
2
2292/3575
oai:researchspace.auckland.ac.nz:2292/3575
2012-02-03 12:23:17.598
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3788
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Chaitin, G.J
2009-04-16T23:10:42Z
2009-04-16T23:10:42Z
2006-07
CDMTCS Research Reports CDMTCS-281 (2006)
1178-3540
http://hdl.handle.net/2292/3788
[no abstract available]
Made available in DSpace on 2009-04-16T23:10:42Z (GMT). No. of bitstreams: 1
281greg.pdf: 104047 bytes, checksum: f81600b8f3543f7445e6807653319d63 (MD5)
Previous issue date: 2006-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Is Incompleteness A Serious Problem
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
281greg.pdf
application/pdf
104047
https://researchspace.auckland.ac.nz/bitstream/2292/3788/1/281greg.pdf
f81600b8f3543f7445e6807653319d63
MD5
1
TEXT
281greg.pdf.txt
281greg.pdf.txt
text/plain
7581
https://researchspace.auckland.ac.nz/bitstream/2292/3788/2/281greg.pdf.txt
f75392a03a4eeedf2e368a122e9fceaf
MD5
2
2292/3788
oai:researchspace.auckland.ac.nz:2292/3788
2012-02-03 12:23:17.684
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3519
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
Dediu, L
2009-04-16T23:10:43Z
2009-04-16T23:10:43Z
1995-10
CDMTCS Research Reports CDMTCS-010 (1995)
1178-3540
http://hdl.handle.net/2292/3519
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.
Made available in DSpace on 2009-04-16T23:10:43Z (GMT). No. of bitstreams: 1
010luminita.pdf: 765510 bytes, checksum: ff28f069ea5691a09430f027b06a917c (MD5)
Previous issue date: 1995-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Higman's Embedding Theorem. An Elementary Proof
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
010luminita.pdf
application/pdf
765510
https://researchspace.auckland.ac.nz/bitstream/2292/3519/1/010luminita.pdf
ff28f069ea5691a09430f027b06a917c
MD5
1
TEXT
010luminita.pdf.txt
010luminita.pdf.txt
text/plain
74752
https://researchspace.auckland.ac.nz/bitstream/2292/3519/2/010luminita.pdf.txt
1b6504553af26e18eecf5151dcf66e61
MD5
2
2292/3519
oai:researchspace.auckland.ac.nz:2292/3519
2012-02-03 12:23:18.597
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3744
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
Juergensen, H
Staiger, L
Yamasaki, H
2009-04-16T23:10:45Z
2009-04-16T23:10:45Z
2004-04
CDMTCS Research Reports CDMTCS-237 (2004)
1178-3540
http://hdl.handle.net/2292/3744
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.
Made available in DSpace on 2009-04-16T23:10:45Z (GMT). No. of bitstreams: 1
237ludwig.pdf: 250800 bytes, checksum: a9249943db07da26e49697d506e5918d (MD5)
Previous issue date: 2004-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Finite Automata Encoding Geometric Figures
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
237ludwig.pdf
application/pdf
250800
https://researchspace.auckland.ac.nz/bitstream/2292/3744/1/237ludwig.pdf
a9249943db07da26e49697d506e5918d
MD5
1
TEXT
237ludwig.pdf.txt
237ludwig.pdf.txt
text/plain
39540
https://researchspace.auckland.ac.nz/bitstream/2292/3744/2/237ludwig.pdf.txt
e23c28020471d2931057ee19831eafb0
MD5
2
2292/3744
oai:researchspace.auckland.ac.nz:2292/3744
2012-02-03 12:23:19.206
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3848
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Müller, C
Kohlhase, M
2009-04-16T23:10:46Z
2009-04-16T23:10:46Z
2008-11
CDMTCS Research Reports CDMTCS-341 (2008)
1178-3540
http://hdl.handle.net/2292/3848
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.
Made available in DSpace on 2009-04-16T23:10:46Z (GMT). No. of bitstreams: 1
341christine.pdf: 612343 bytes, checksum: c6b12eb4db922deca29ab32bc99d6d8e (MD5)
Previous issue date: 2008-11
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Context-Aware Adaptation. A Case Study on Mathematical Notations
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
341christine.pdf
application/pdf
612343
https://researchspace.auckland.ac.nz/bitstream/2292/3848/1/341christine.pdf
c6b12eb4db922deca29ab32bc99d6d8e
MD5
1
TEXT
341christine.pdf.txt
341christine.pdf.txt
text/plain
91964
https://researchspace.auckland.ac.nz/bitstream/2292/3848/2/341christine.pdf.txt
33074f2cc22731ee74bfa494d294de1d
MD5
2
2292/3848
oai:researchspace.auckland.ac.nz:2292/3848
2012-02-03 12:23:14.127
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3775
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Greenberger, D.M
Svozil, K
2009-04-16T23:10:48Z
2009-04-16T23:10:48Z
2005-06
CDMTCS Research Reports CDMTCS-268 (2005)
1178-3540
http://hdl.handle.net/2292/3775
We introduce a quantum mechanical model of time travel which includes two figurative beam splitters in
order to induce feedback to earlier times. This leads to a unique solution to the paradox where one could kill
one’s grandfather in that once the future has unfolded, it cannot change the past, and so the past becomes
deterministic. On the other hand, looking forwards towards the future is completely probabilistic. This
resolves the classical paradox in a philosophically satisfying manner.
Made available in DSpace on 2009-04-16T23:10:48Z (GMT). No. of bitstreams: 1
268karl.pdf: 132264 bytes, checksum: 2bd72e7ae6a431d92349384bb7308e31 (MD5)
Previous issue date: 2005-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Quantum Theory Looks at Time Travel
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
268karl.pdf
application/pdf
132264
https://researchspace.auckland.ac.nz/bitstream/2292/3775/1/268karl.pdf
2bd72e7ae6a431d92349384bb7308e31
MD5
1
TEXT
268karl.pdf.txt
268karl.pdf.txt
text/plain
19105
https://researchspace.auckland.ac.nz/bitstream/2292/3775/2/268karl.pdf.txt
4d3b27c49b7dc2d20f7f8c39e6f1f77a
MD5
2
2292/3775
oai:researchspace.auckland.ac.nz:2292/3775
2012-02-03 12:23:16.662
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3660
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Calude, C.S
Dinneen, Michael
Sburlan, S
2009-04-16T23:10:49Z
2009-04-16T23:10:49Z
2001-04
CDMTCS Research Reports CDMTCS-152 (2001)
1178-3540
http://hdl.handle.net/2292/3660
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.
Made available in DSpace on 2009-04-16T23:10:49Z (GMT). No. of bitstreams: 1
152DMTCS01.pdf: 242160 bytes, checksum: 43960ae266f44f3507fa08a7bd8bb83d (MD5)
Previous issue date: 2001-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Supplemental Abstracts for DMTCS01
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
152DMTCS01.pdf
application/pdf
242160
https://researchspace.auckland.ac.nz/bitstream/2292/3660/1/152DMTCS01.pdf
43960ae266f44f3507fa08a7bd8bb83d
MD5
1
TEXT
152DMTCS01.pdf.txt
152DMTCS01.pdf.txt
text/plain
154268
https://researchspace.auckland.ac.nz/bitstream/2292/3660/2/152DMTCS01.pdf.txt
744dcfa8c645e1e9d74d625a22af9060
MD5
2
2292/3660
oai:researchspace.auckland.ac.nz:2292/3660
2012-02-03 12:23:14.051
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3663
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
Donath, N
Svozil, K
2009-04-16T23:10:51Z
2009-04-16T23:10:51Z
2001-05
CDMTCS Research Reports CDMTCS-155 (2001)
1178-3540
http://hdl.handle.net/2292/3663
We consider the problem to single out a particular state among 2n orthogonal pure states. As it turns out, in general the optimal strategy is not to measure the particles separately, but to consider joint properties of the n-particle system. The required number of propositions is n. There exist 2n! equivalent operational procedures to do so. We enumerate some configurations for three particles, in particular the Greenberger-Horne-Zeilinger (GHZ) and W-states, which are specific cases of a unitary transformation. For the GHZ-case, an explicit physical meaning of the projection operators is discussed.
Made available in DSpace on 2009-04-16T23:10:51Z (GMT). No. of bitstreams: 1
155karl.pdf: 197634 bytes, checksum: 3a4f471acb3fdf7991cd6f09a31cf1fe (MD5)
Previous issue date: 2001-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Finding a State in a Haystack
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
155karl.pdf
application/pdf
197634
https://researchspace.auckland.ac.nz/bitstream/2292/3663/1/155karl.pdf
3a4f471acb3fdf7991cd6f09a31cf1fe
MD5
1
TEXT
155karl.pdf.txt
155karl.pdf.txt
text/plain
115367
https://researchspace.auckland.ac.nz/bitstream/2292/3663/2/155karl.pdf.txt
f72f5f666308b9a775eb9ccea9858280
MD5
2
2292/3663
oai:researchspace.auckland.ac.nz:2292/3663
2012-02-03 12:23:18.504
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3719
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Terwijn, S.A
2009-04-16T23:10:52Z
2009-04-16T23:10:52Z
2003-03
CDMTCS Research Reports CDMTCS-212 (2003)
1178-3540
http://hdl.handle.net/2292/3719
[no abstract available]
Made available in DSpace on 2009-04-16T23:10:52Z (GMT). No. of bitstreams: 1
212bas.pdf: 447284 bytes, checksum: fe1dad5266463e14fa2c3060df03ebd9 (MD5)
Previous issue date: 2003-03
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Complexity and Randomness
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
212bas.pdf
application/pdf
447284
https://researchspace.auckland.ac.nz/bitstream/2292/3719/1/212bas.pdf
fe1dad5266463e14fa2c3060df03ebd9
MD5
1
TEXT
212bas.pdf.txt
212bas.pdf.txt
text/plain
84665
https://researchspace.auckland.ac.nz/bitstream/2292/3719/2/212bas.pdf.txt
65f7289fd7e4f527eda676a2a4805ab7
MD5
2
2292/3719
oai:researchspace.auckland.ac.nz:2292/3719
2012-02-03 12:23:13.233
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3626
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Calude, C.S
Paun, G
Tataram, Monica
2009-04-16T23:10:54Z
2009-04-16T23:10:54Z
1999-12
CDMTCS Research Reports CDMTCS-117 (1999)
1178-3540
http://hdl.handle.net/2292/3626
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.
Made available in DSpace on 2009-04-16T23:10:54Z (GMT). No. of bitstreams: 1
117cris.pdf: 241880 bytes, checksum: 6db071c5a51f1e7976bc51fd07878d60 (MD5)
Previous issue date: 1999-12
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Glimpse into Natural Computing
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
117cris.pdf
application/pdf
241880
https://researchspace.auckland.ac.nz/bitstream/2292/3626/1/117cris.pdf
6db071c5a51f1e7976bc51fd07878d60
MD5
1
TEXT
117cris.pdf.txt
117cris.pdf.txt
text/plain
56517
https://researchspace.auckland.ac.nz/bitstream/2292/3626/2/117cris.pdf.txt
fd35a89bf7af30cb376b44b39f52c250
MD5
2
2292/3626
oai:researchspace.auckland.ac.nz:2292/3626
2012-02-03 12:23:16.117
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3776
2012-02-02T23:23:12Z
com_2292_122
col_2292_3508
Svozil, K
2009-04-16T23:10:56Z
2009-04-16T23:10:56Z
2005-06
CDMTCS Research Reports CDMTCS-269 (2005)
1178-3540
http://hdl.handle.net/2292/3776
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.
Made available in DSpace on 2009-04-16T23:10:56Z (GMT). No. of bitstreams: 1
269karl.pdf: 142097 bytes, checksum: 2559303cf827d8457625674872464270 (MD5)
Previous issue date: 2005-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Characterization of Quantum Computable Decision Problems by State Discrimination
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
269karl.pdf
application/pdf
142097
https://researchspace.auckland.ac.nz/bitstream/2292/3776/1/269karl.pdf
2559303cf827d8457625674872464270
MD5
1
TEXT
269karl.pdf.txt
269karl.pdf.txt
text/plain
32356
https://researchspace.auckland.ac.nz/bitstream/2292/3776/2/269karl.pdf.txt
f1869486874510f12af98e98b47c96db
MD5
2
2292/3776
oai:researchspace.auckland.ac.nz:2292/3776
2012-02-03 12:23:12.986
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3641
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
Pavlov, B
2009-04-16T23:10:57Z
2009-04-16T23:10:57Z
2000-05
CDMTCS Research Reports CDMTCS-132 (2000)
1178-3540
http://hdl.handle.net/2292/3641
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.
Made available in DSpace on 2009-04-16T23:10:57Z (GMT). No. of bitstreams: 1
132cris.pdf: 692509 bytes, checksum: e4b932bafb165c1f496acc9d9a38d1aa (MD5)
Previous issue date: 2000-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
The Poincare-Hardy Inequality on the Complement of a Cantor Set
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
132cris.pdf
application/pdf
692509
https://researchspace.auckland.ac.nz/bitstream/2292/3641/1/132cris.pdf
e4b932bafb165c1f496acc9d9a38d1aa
MD5
1
TEXT
132cris.pdf.txt
132cris.pdf.txt
text/plain
34435
https://researchspace.auckland.ac.nz/bitstream/2292/3641/2/132cris.pdf.txt
07abdc1ddff814b593f5a85907bc2c74
MD5
2
2292/3641
oai:researchspace.auckland.ac.nz:2292/3641
2012-02-03 12:23:15.021
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3868
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Svozil, K
2009-04-16T23:10:58Z
2009-04-16T23:10:58Z
2009-04
CDMTCS Research Reports CDMTCS-362 (2009)
1178-3540
http://hdl.handle.net/2292/3868
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.
Made available in DSpace on 2009-04-16T23:10:58Z (GMT). No. of bitstreams: 1
362karl.pdf: 157516 bytes, checksum: a204cf9de5131b548bb1866e9dc3180f (MD5)
Previous issue date: 2009-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Three Criteria for Quantum Random Number Generators Based on Beam Splitters
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
362karl.pdf
application/pdf
157516
https://researchspace.auckland.ac.nz/bitstream/2292/3868/1/362karl.pdf
a204cf9de5131b548bb1866e9dc3180f
MD5
1
TEXT
362karl.pdf.txt
362karl.pdf.txt
text/plain
19716
https://researchspace.auckland.ac.nz/bitstream/2292/3868/2/362karl.pdf.txt
1b3ff086fe14fc270af62d4bd0d50bd3
MD5
2
2292/3868
oai:researchspace.auckland.ac.nz:2292/3868
2012-02-03 12:23:14.066
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3819
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
Staiger, L
2009-04-16T23:11:00Z
2009-04-16T23:11:00Z
2007-10
CDMTCS Research Reports CDMTCS-312 (2007)
1178-3540
http://hdl.handle.net/2292/3819
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.
Made available in DSpace on 2009-04-16T23:11:00Z (GMT). No. of bitstreams: 1
312cris.pdf: 263868 bytes, checksum: 2d3284d05ed2117f12df4981a23a6eac (MD5)
Previous issue date: 2007-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
On Universal Computably Enumerable Prefix Codes
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
312cris.pdf
application/pdf
263868
https://researchspace.auckland.ac.nz/bitstream/2292/3819/1/312cris.pdf
2d3284d05ed2117f12df4981a23a6eac
MD5
1
TEXT
312cris.pdf.txt
312cris.pdf.txt
text/plain
28217
https://researchspace.auckland.ac.nz/bitstream/2292/3819/2/312cris.pdf.txt
fd011d9d3b18d6b502b3a37c5ed5e12c
MD5
2
2292/3819
oai:researchspace.auckland.ac.nz:2292/3819
2012-02-03 12:23:15.42
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3746
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Calude, C.S
Staiger, L
Terwijn, S.A
2009-04-16T23:11:01Z
2009-04-16T23:11:01Z
2004-04
CDMTCS Research Reports CDMTCS-239 (2004)
1178-3540
http://hdl.handle.net/2292/3746
[no abstract available]
Made available in DSpace on 2009-04-16T23:11:01Z (GMT). No. of bitstreams: 1
239cris.pdf: 190034 bytes, checksum: 77ef46176e024cd61e8911e9d589009d (MD5)
Previous issue date: 2004-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
On Partial Randomness
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
239cris.pdf
application/pdf
190034
https://researchspace.auckland.ac.nz/bitstream/2292/3746/1/239cris.pdf
77ef46176e024cd61e8911e9d589009d
MD5
1
TEXT
239cris.pdf.txt
239cris.pdf.txt
text/plain
26814
https://researchspace.auckland.ac.nz/bitstream/2292/3746/2/239cris.pdf.txt
a89fbf749e9d746ba11bf8e0962c1923
MD5
2
2292/3746
oai:researchspace.auckland.ac.nz:2292/3746
2012-02-03 12:23:14.623
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3606
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Kraegeloh, A.M
2009-04-16T23:11:02Z
2009-04-16T23:11:02Z
1999-03
CDMTCS Research Reports CDMTCS-097 (1999)
1178-3540
http://hdl.handle.net/2292/3606
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.
Made available in DSpace on 2009-04-16T23:11:02Z (GMT). No. of bitstreams: 1
097alexander.pdf: 1065308 bytes, checksum: f4cec04c42198c8ec56f54b38cd2bb82 (MD5)
Previous issue date: 1999-03
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Unstable Dynamics on a Markov Background and Stability in Average
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
097alexander.pdf
application/pdf
1065308
https://researchspace.auckland.ac.nz/bitstream/2292/3606/1/097alexander.pdf
f4cec04c42198c8ec56f54b38cd2bb82
MD5
1
TEXT
097alexander.pdf.txt
097alexander.pdf.txt
text/plain
232627
https://researchspace.auckland.ac.nz/bitstream/2292/3606/2/097alexander.pdf.txt
79a4ca5f1827792c283f03cccba602a9
MD5
2
2292/3606
oai:researchspace.auckland.ac.nz:2292/3606
2012-02-03 12:23:17.925
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3595
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
Merkle, W
Wang, Y
2009-04-16T23:11:04Z
2009-04-16T23:11:04Z
1998-05
CDMTCS Research Reports CDMTCS-086 (1998)
1178-3540
http://hdl.handle.net/2292/3595
The concept of pseudorandomness plays an important role in cryptography. In this note we contrast the notions of complexity-theoretic pseudorandom strings (from algorithmic information theory) and pseudorandom strings (from cryptography). For example, we show that we can easily distinguish a complexity-theoretic pseudorandom ensemble from the uniform ensemble. Both notions of pseudorandom strings are uniformly unpredictable; in contrast with pseudorandom strings, complexity-theoretic pseudorandom strings are not polynomial-time unpredictable.
Made available in DSpace on 2009-04-16T23:11:04Z (GMT). No. of bitstreams: 1
086randgen.pdf: 211023 bytes, checksum: 9955c225a78dcf3e9f1c5a59f5b776d8 (MD5)
Previous issue date: 1998-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Note on Pseudorandom Generators
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
086randgen.pdf
application/pdf
211023
https://researchspace.auckland.ac.nz/bitstream/2292/3595/1/086randgen.pdf
9955c225a78dcf3e9f1c5a59f5b776d8
MD5
1
TEXT
086randgen.pdf.txt
086randgen.pdf.txt
text/plain
19771
https://researchspace.auckland.ac.nz/bitstream/2292/3595/2/086randgen.pdf.txt
591942142e1490789445ae61e2257973
MD5
2
2292/3595
oai:researchspace.auckland.ac.nz:2292/3595
2012-02-03 12:23:15.715
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3745
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Filipp, S
Svozil, K
2009-04-16T23:11:05Z
2009-04-16T23:11:05Z
2004-04
CDMTCS Research Reports CDMTCS-238 (2004)
1178-3540
http://hdl.handle.net/2292/3745
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.
Made available in DSpace on 2009-04-16T23:11:05Z (GMT). No. of bitstreams: 1
238karl.pdf: 90834 bytes, checksum: fc10b1a9f758175a3d15b1dbdc22015f (MD5)
Previous issue date: 2004-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
The min-max Principle Generalizes Tsirelson's Bound
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
238karl.pdf
application/pdf
90834
https://researchspace.auckland.ac.nz/bitstream/2292/3745/1/238karl.pdf
fc10b1a9f758175a3d15b1dbdc22015f
MD5
1
TEXT
238karl.pdf.txt
238karl.pdf.txt
text/plain
17655
https://researchspace.auckland.ac.nz/bitstream/2292/3745/2/238karl.pdf.txt
a5d140e2754fe39c20891eea8f1b739b
MD5
2
2292/3745
oai:researchspace.auckland.ac.nz:2292/3745
2012-02-03 12:23:16.16
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3818
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Drape, S
Majumdar, A
2009-04-16T23:11:07Z
2009-04-16T23:11:07Z
2007-06
CDMTCS Research Reports CDMTCS-311 (2007)
1178-3540
http://hdl.handle.net/2292/3818
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.
Made available in DSpace on 2009-04-16T23:11:07Z (GMT). No. of bitstreams: 1
311stephen.pdf: 440438 bytes, checksum: ce5bfcc2319e1697b4c153002b8c5ce1 (MD5)
Previous issue date: 2007-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Design and Evaluation of Slicing Obfuscation
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
311stephen.pdf
application/pdf
440438
https://researchspace.auckland.ac.nz/bitstream/2292/3818/1/311stephen.pdf
ce5bfcc2319e1697b4c153002b8c5ce1
MD5
1
TEXT
311stephen.pdf.txt
311stephen.pdf.txt
text/plain
101710
https://researchspace.auckland.ac.nz/bitstream/2292/3818/2/311stephen.pdf.txt
71851dd982427289fa9748aefa1e8bba
MD5
2
2292/3818
oai:researchspace.auckland.ac.nz:2292/3818
2012-02-03 12:23:16.909
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3688
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Calude, C.S
Calude, E
Marcus, S
2009-04-16T23:11:08Z
2009-04-16T23:11:08Z
2002-02
CDMTCS Research Reports CDMTCS-180 (2002)
1178-3540
http://hdl.handle.net/2292/3688
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.
Made available in DSpace on 2009-04-16T23:11:08Z (GMT). No. of bitstreams: 1
180proofs.pdf: 448177 bytes, checksum: 902ba494ad2ee8dc162aac5e38384861 (MD5)
Previous issue date: 2002-02
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Passages of Proof
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
180proofs.pdf
application/pdf
448177
https://researchspace.auckland.ac.nz/bitstream/2292/3688/1/180proofs.pdf
902ba494ad2ee8dc162aac5e38384861
MD5
1
TEXT
180proofs.pdf.txt
180proofs.pdf.txt
text/plain
60634
https://researchspace.auckland.ac.nz/bitstream/2292/3688/2/180proofs.pdf.txt
2e849bbf784e2aa65189376de2a3724a
MD5
2
2292/3688
oai:researchspace.auckland.ac.nz:2292/3688
2012-02-03 12:23:17.759
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3720
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
Staiger, L
Svozil, K
2009-04-16T23:11:10Z
2009-04-16T23:11:10Z
2003-04
CDMTCS Research Reports CDMTCS-213 (2003)
1178-3540
http://hdl.handle.net/2292/3720
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.
Made available in DSpace on 2009-04-16T23:11:10Z (GMT). No. of bitstreams: 1
213cris.pdf: 210324 bytes, checksum: 1f66ad2a508ea08a4f5e6bb8cbef53fe (MD5)
Previous issue date: 2003-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Randomness Relative to Cantor Expansions
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
213cris.pdf
application/pdf
210324
https://researchspace.auckland.ac.nz/bitstream/2292/3720/1/213cris.pdf
1f66ad2a508ea08a4f5e6bb8cbef53fe
MD5
1
TEXT
213cris.pdf.txt
213cris.pdf.txt
text/plain
24564
https://researchspace.auckland.ac.nz/bitstream/2292/3720/2/213cris.pdf.txt
9082dabd0e5e88d6aae14fc0a33368ae
MD5
2
2292/3720
oai:researchspace.auckland.ac.nz:2292/3720
2012-02-03 12:23:13.952
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3846
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Calude, C.S
2009-04-16T23:11:11Z
2009-04-16T23:11:11Z
2008-11
CDMTCS Research Reports CDMTCS-339 (2008)
1178-3540
http://hdl.handle.net/2292/3846
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.
Made available in DSpace on 2009-04-16T23:11:11Z (GMT). No. of bitstreams: 1
339cris.pdf: 341042 bytes, checksum: 2a92f614eb3cb6dfd13e296b81c4e739 (MD5)
Previous issue date: 2008-11
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Simplicity via Provability for Universal Prefix-free Turing Machines
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
339cris.pdf
application/pdf
341042
https://researchspace.auckland.ac.nz/bitstream/2292/3846/1/339cris.pdf
2a92f614eb3cb6dfd13e296b81c4e739
MD5
1
TEXT
339cris.pdf.txt
339cris.pdf.txt
text/plain
17476
https://researchspace.auckland.ac.nz/bitstream/2292/3846/2/339cris.pdf.txt
0607710be1263c9546266705eb3c5ade
MD5
2
2292/3846
oai:researchspace.auckland.ac.nz:2292/3846
2012-02-03 12:23:17.834
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3813
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Calude, C.S
Gruska, J
2009-04-16T23:11:12Z
2009-04-16T23:11:12Z
2007-05
CDMTCS Research Reports CDMTCS-306 (2007)
1178-3540
http://hdl.handle.net/2292/3813
[no abstract available]
Made available in DSpace on 2009-04-16T23:11:12Z (GMT). No. of bitstreams: 1
306cris.pdf: 372078 bytes, checksum: c90564ee78b39e56601222ab7126c2c6 (MD5)
Previous issue date: 2007-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Quantum Informatics and the Relations Between Informatics, Physics and Mathematics: A Dialogue
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
306cris.pdf
application/pdf
372078
https://researchspace.auckland.ac.nz/bitstream/2292/3813/1/306cris.pdf
c90564ee78b39e56601222ab7126c2c6
MD5
1
TEXT
306cris.pdf.txt
306cris.pdf.txt
text/plain
69025
https://researchspace.auckland.ac.nz/bitstream/2292/3813/2/306cris.pdf.txt
0ad8d4942d0ff59beea3be6461954b58
MD5
2
2292/3813
oai:researchspace.auckland.ac.nz:2292/3813
2012-02-03 12:23:14.724
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3545
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Calude, C.S
Hertling, P.H
Svozil, K
2009-04-16T23:11:15Z
2009-04-16T23:11:15Z
1997-05
CDMTCS Research Reports CDMTCS-036 (1997)
1178-3540
http://hdl.handle.net/2292/3545
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.
Made available in DSpace on 2009-04-16T23:11:15Z (GMT). No. of bitstreams: 1
036cris.pdf: 494485 bytes, checksum: ff70d0433bab75a1f5c5be3f6ed28354 (MD5)
Previous issue date: 1997-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Embedding Quantum Universes into Classical Ones
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
036cris.pdf
application/pdf
494485
https://researchspace.auckland.ac.nz/bitstream/2292/3545/1/036cris.pdf
ff70d0433bab75a1f5c5be3f6ed28354
MD5
1
TEXT
036cris.pdf.txt
036cris.pdf.txt
text/plain
57351
https://researchspace.auckland.ac.nz/bitstream/2292/3545/2/036cris.pdf.txt
beb71f7d8c5bc37f5e46e6cf080789cc
MD5
2
2292/3545
oai:researchspace.auckland.ac.nz:2292/3545
2012-02-03 12:23:14.17
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3794
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Pritchard, G
Wilson, Mark
2009-04-16T23:11:16Z
2009-04-16T23:11:16Z
2006-10
CDMTCS Research Reports CDMTCS-287 (2006)
1178-3540
http://hdl.handle.net/2292/3794
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.
Made available in DSpace on 2009-04-16T23:11:16Z (GMT). No. of bitstreams: 1
287wilson.pdf: 167923 bytes, checksum: 71bc8f5a4f9b2e1a21faa2f84b549193 (MD5)
Previous issue date: 2006-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Probability Calculations Under the IAC Hypothesis
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
287wilson.pdf
application/pdf
167923
https://researchspace.auckland.ac.nz/bitstream/2292/3794/1/287wilson.pdf
71bc8f5a4f9b2e1a21faa2f84b549193
MD5
1
TEXT
287wilson.pdf.txt
287wilson.pdf.txt
text/plain
32478
https://researchspace.auckland.ac.nz/bitstream/2292/3794/2/287wilson.pdf.txt
942f924c66db38e85f547dfaec55b05a
MD5
2
2292/3794
oai:researchspace.auckland.ac.nz:2292/3794
2012-02-03 12:23:16.633
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3814
2020-03-10T02:14:36Z
com_2292_122
col_2292_3508
Raichev, A
Wilson, Mark
2009-04-16T23:11:17Z
2009-04-16T23:11:17Z
2007-05
CDMTCS Research Reports CDMTCS-307 (2007)
1178-3540
http://hdl.handle.net/2292/3814
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].
Made available in DSpace on 2009-04-16T23:11:17Z (GMT). No. of bitstreams: 1
307mcw.pdf: 212739 bytes, checksum: a8cde19d80b86fff7323db9045154ac2 (MD5)
Previous issue date: 2007-05
Department of Computer Science, The University of Auckland, New Zealand
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
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Asymptotics of Diagonal Coefficients of Multivariate Generating Functions
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
307mcw.pdf
application/pdf
212739
https://researchspace.auckland.ac.nz/bitstream/2292/3814/1/307mcw.pdf
a8cde19d80b86fff7323db9045154ac2
MD5
1
TEXT
307mcw.pdf.txt
307mcw.pdf.txt
text/plain
17750
https://researchspace.auckland.ac.nz/bitstream/2292/3814/2/307mcw.pdf.txt
bdfcb5210b0cf0eb6371889e18080697
MD5
2
2292/3814
oai:researchspace.auckland.ac.nz:2292/3814
2020-03-10 15:14:36.853
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3590
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
Arslanov, A
2009-04-16T23:11:19Z
2009-04-16T23:11:19Z
1998-04
CDMTCS Research Reports CDMTCS-081 (1998)
1178-3540
http://hdl.handle.net/2292/3590
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.
Made available in DSpace on 2009-04-16T23:11:19Z (GMT). No. of bitstreams: 1
081asat.pdf: 338106 bytes, checksum: ccfc18bb939eca294c7006aea3e46617 (MD5)
Previous issue date: 1998-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
On Hypersimple Sets and Chaitin Complexity
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
081asat.pdf
application/pdf
338106
https://researchspace.auckland.ac.nz/bitstream/2292/3590/1/081asat.pdf
ccfc18bb939eca294c7006aea3e46617
MD5
1
TEXT
081asat.pdf.txt
081asat.pdf.txt
text/plain
23179
https://researchspace.auckland.ac.nz/bitstream/2292/3590/2/081asat.pdf.txt
010fa993d4d0e5a41e152ff69e63640d
MD5
2
2292/3590
oai:researchspace.auckland.ac.nz:2292/3590
2012-02-03 12:23:18.664
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3666
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Grozea, C
2009-04-16T23:11:20Z
2009-04-16T23:11:20Z
2001-07
CDMTCS Research Reports CDMTCS-158 (2001)
1178-3540
http://hdl.handle.net/2292/3666
[no abstract available]
Made available in DSpace on 2009-04-16T23:11:20Z (GMT). No. of bitstreams: 1
158grozea.pdf: 3007070 bytes, checksum: 229e7b3d06cbd6a21b4d74866caeff51 (MD5)
Previous issue date: 2001-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Relations Between the Low Subrecursion Classes
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
158grozea.pdf
application/pdf
3007070
https://researchspace.auckland.ac.nz/bitstream/2292/3666/1/158grozea.pdf
229e7b3d06cbd6a21b4d74866caeff51
MD5
1
TEXT
158grozea.pdf.txt
158grozea.pdf.txt
text/plain
12
https://researchspace.auckland.ac.nz/bitstream/2292/3666/2/158grozea.pdf.txt
36c6f0b2061da514c400c0bc2749b5cf
MD5
2
2292/3666
oai:researchspace.auckland.ac.nz:2292/3666
2012-02-03 12:23:17.819
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3547
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Richman, F
Bridges, D.S
2009-04-16T23:11:22Z
2009-04-16T23:11:22Z
1997-05
CDMTCS Research Reports CDMTCS-038 (1997)
1178-3540
http://hdl.handle.net/2292/3547
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
Made available in DSpace on 2009-04-16T23:11:22Z (GMT). No. of bitstreams: 1
038douglas.pdf: 297780 bytes, checksum: b1b180450d01aef2acaecc1f9d420075 (MD5)
Previous issue date: 1997-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Constructive Proof of Gleason's Theorem
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
038douglas.pdf
application/pdf
297780
https://researchspace.auckland.ac.nz/bitstream/2292/3547/1/038douglas.pdf
b1b180450d01aef2acaecc1f9d420075
MD5
1
TEXT
038douglas.pdf.txt
038douglas.pdf.txt
text/plain
50757
https://researchspace.auckland.ac.nz/bitstream/2292/3547/2/038douglas.pdf.txt
9e2deaba65983ab15eabe0ef8dca05a0
MD5
2
2292/3547
oai:researchspace.auckland.ac.nz:2292/3547
2012-02-03 12:23:13.559
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3669
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Calude, C.S
Calude, E
2009-04-16T23:11:24Z
2009-04-16T23:11:24Z
2001-09
CDMTCS Research Reports CDMTCS-161 (2001)
1178-3540
http://hdl.handle.net/2292/3669
In this note we solve the general case of the Bridge Crossing Problem.
Made available in DSpace on 2009-04-16T23:11:24Z (GMT). No. of bitstreams: 1
161CE.pdf: 518623 bytes, checksum: fdc515b484fc2276d954e57047276048 (MD5)
Previous issue date: 2001-09
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
The Bridge Crossing Problem: Draft Form
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
161CE.pdf
application/pdf
518623
https://researchspace.auckland.ac.nz/bitstream/2292/3669/1/161CE.pdf
fdc515b484fc2276d954e57047276048
MD5
1
TEXT
161CE.pdf.txt
161CE.pdf.txt
text/plain
18070
https://researchspace.auckland.ac.nz/bitstream/2292/3669/2/161CE.pdf.txt
20953aa70f8ea5ba1ae37c5a8ff7ff6c
MD5
2
2292/3669
oai:researchspace.auckland.ac.nz:2292/3669
2012-02-03 12:23:17.533
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3599
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
Coles, R.J
Hertling, P.H
Khoussainov, B
2009-04-16T23:11:25Z
2009-04-16T23:11:25Z
1998-09
CDMTCS Research Reports CDMTCS-090 (1998)
1178-3540
http://hdl.handle.net/2292/3599
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 α.
Made available in DSpace on 2009-04-16T23:11:25Z (GMT). No. of bitstreams: 1
090cris.pdf: 333168 bytes, checksum: 67a00d1f8359da64298100fcdc5e7f08 (MD5)
Previous issue date: 1998-09
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Degree-Theoretic Aspects of Computably Enumerable Reals
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
090cris.pdf
application/pdf
333168
https://researchspace.auckland.ac.nz/bitstream/2292/3599/1/090cris.pdf
67a00d1f8359da64298100fcdc5e7f08
MD5
1
TEXT
090cris.pdf.txt
090cris.pdf.txt
text/plain
50449
https://researchspace.auckland.ac.nz/bitstream/2292/3599/2/090cris.pdf.txt
04ed766a573e23f2d723feff21894990
MD5
2
2292/3599
oai:researchspace.auckland.ac.nz:2292/3599
2012-02-03 12:23:13.431
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3750
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Stay, M
2009-04-16T23:11:26Z
2009-04-16T23:11:26Z
2004-07
CDMTCS Research Reports CDMTCS-243 (2004)
1178-3540
http://hdl.handle.net/2292/3750
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.
Made available in DSpace on 2009-04-16T23:11:26Z (GMT). No. of bitstreams: 1
243mike.pdf: 353070 bytes, checksum: 1180b71ec00b75a458b6a452037b7f45 (MD5)
Previous issue date: 2004-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Inexpensive Linear-Optical Implementations of Deutsch's Algorithm
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
243mike.pdf
application/pdf
353070
https://researchspace.auckland.ac.nz/bitstream/2292/3750/1/243mike.pdf
1180b71ec00b75a458b6a452037b7f45
MD5
1
TEXT
243mike.pdf.txt
243mike.pdf.txt
text/plain
11433
https://researchspace.auckland.ac.nz/bitstream/2292/3750/2/243mike.pdf.txt
b749750901baeee742271e40f4925d62
MD5
2
2292/3750
oai:researchspace.auckland.ac.nz:2292/3750
2012-02-03 12:23:15.336
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3714
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Khoussainov, B
Kowalski, T
2009-04-16T23:11:28Z
2009-04-16T23:11:28Z
2003-01
CDMTCS Research Reports CDMTCS-207 (2003)
1178-3540
http://hdl.handle.net/2292/3714
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
Made available in DSpace on 2009-04-16T23:11:28Z (GMT). No. of bitstreams: 1
207bmk.pdf: 228137 bytes, checksum: 78287d1fcc3d12ed079ba2efafb2eb84 (MD5)
Previous issue date: 2003-01
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Games on Graphs: Automata, Structure, and Complexity
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
207bmk.pdf
application/pdf
228137
https://researchspace.auckland.ac.nz/bitstream/2292/3714/1/207bmk.pdf
78287d1fcc3d12ed079ba2efafb2eb84
MD5
1
TEXT
207bmk.pdf.txt
207bmk.pdf.txt
text/plain
39289
https://researchspace.auckland.ac.nz/bitstream/2292/3714/2/207bmk.pdf.txt
75a93b8bdc45f08c02d1de44a0a2aa04
MD5
2
2292/3714
oai:researchspace.auckland.ac.nz:2292/3714
2012-02-03 12:23:14.901
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3548
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Calude, C.S
2009-04-16T23:11:29Z
2009-04-16T23:11:29Z
1997-06
CDMTCS Research Reports CDMTCS-039 (1997)
1178-3540
http://hdl.handle.net/2292/3548
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
Made available in DSpace on 2009-04-16T23:11:29Z (GMT). No. of bitstreams: 1
039cris.pdf: 254901 bytes, checksum: 94b89e43a5444afcc4e5e438a91e2d19 (MD5)
Previous issue date: 1997-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A Genius' Story: Two Books on Godel
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
039cris.pdf
application/pdf
254901
https://researchspace.auckland.ac.nz/bitstream/2292/3548/1/039cris.pdf
94b89e43a5444afcc4e5e438a91e2d19
MD5
1
TEXT
039cris.pdf.txt
039cris.pdf.txt
text/plain
26284
https://researchspace.auckland.ac.nz/bitstream/2292/3548/2/039cris.pdf.txt
39cc90433177ff46566b422da9832ae0
MD5
2
2292/3548
oai:researchspace.auckland.ac.nz:2292/3548
2012-02-03 12:23:16.072
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3623
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
2009-04-16T23:11:31Z
2009-04-16T23:11:31Z
1999-10
CDMTCS Research Reports CDMTCS-114 (1999)
1178-3540
http://hdl.handle.net/2292/3623
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.
Made available in DSpace on 2009-04-16T23:11:31Z (GMT). No. of bitstreams: 1
114cris.pdf: 158645 bytes, checksum: 28fe0a56fb10039dc58b821668ffde03 (MD5)
Previous issue date: 1999-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Chaitin $\Omega$ Numbers, Solovay Machines, and Incompleteness
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
114cris.pdf
application/pdf
158645
https://researchspace.auckland.ac.nz/bitstream/2292/3623/1/114cris.pdf
28fe0a56fb10039dc58b821668ffde03
MD5
1
TEXT
114cris.pdf.txt
114cris.pdf.txt
text/plain
19322
https://researchspace.auckland.ac.nz/bitstream/2292/3623/2/114cris.pdf.txt
77209067a907051ced0515596b7fe530
MD5
2
2292/3623
oai:researchspace.auckland.ac.nz:2292/3623
2012-02-03 12:23:13.328
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3767
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Ishihara, H
Mines, R
Schuster, P
Vita, L.S
2009-04-16T23:11:32Z
2009-04-16T23:11:32Z
2005-03
CDMTCS Research Reports CDMTCS-260 (2005)
1178-3540
http://hdl.handle.net/2292/3767
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.
Made available in DSpace on 2009-04-16T23:11:32Z (GMT). No. of bitstreams: 1
260hajime.pdf: 261363 bytes, checksum: c2a6a1874379084ec8980036eadee2bb (MD5)
Previous issue date: 2005-03
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Quasi-Apartness and Neighbourhood Spaces
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
260hajime.pdf
application/pdf
261363
https://researchspace.auckland.ac.nz/bitstream/2292/3767/1/260hajime.pdf
c2a6a1874379084ec8980036eadee2bb
MD5
1
TEXT
260hajime.pdf.txt
260hajime.pdf.txt
text/plain
141954
https://researchspace.auckland.ac.nz/bitstream/2292/3767/2/260hajime.pdf.txt
de712be7cc1a5e297800126ac9de46d9
MD5
2
2292/3767
oai:researchspace.auckland.ac.nz:2292/3767
2012-02-03 12:23:17.114
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3753
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
Paun, G
2009-04-16T23:11:33Z
2009-04-16T23:11:33Z
2004-08
CDMTCS Research Reports CDMTCS-246 (2004)
1178-3540
http://hdl.handle.net/2292/3753
This is the text added to the Russian edition of our book Computing with
Cells and Atoms (Taylor & Francis Publishers, London, 2001) to be published
by Pushchino Publishing House. The translation was done by Professor Victor
Vladimirovich Ivanov and Professor Robert Polozov.
Made available in DSpace on 2009-04-16T23:11:33Z (GMT). No. of bitstreams: 1
246cris.pdf: 218231 bytes, checksum: 89acc4ee5383d61b0ac4b0bfcde976c6 (MD5)
Previous issue date: 2004-08
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Computing with Cells and Atoms: After Five Years
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
246cris.pdf
application/pdf
218231
https://researchspace.auckland.ac.nz/bitstream/2292/3753/1/246cris.pdf
89acc4ee5383d61b0ac4b0bfcde976c6
MD5
1
TEXT
246cris.pdf.txt
246cris.pdf.txt
text/plain
63368
https://researchspace.auckland.ac.nz/bitstream/2292/3753/2/246cris.pdf.txt
0ea2f0980fe39502e25a894a4308619c
MD5
2
2292/3753
oai:researchspace.auckland.ac.nz:2292/3753
2012-02-03 12:23:13.412
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3692
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Svozil, K
2009-04-16T23:11:35Z
2009-04-16T23:11:35Z
2002-05
CDMTCS Research Reports CDMTCS-184 (2002)
1178-3540
http://hdl.handle.net/2292/3692
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.
Made available in DSpace on 2009-04-16T23:11:35Z (GMT). No. of bitstreams: 1
184karl.pdf: 69224 bytes, checksum: ce95daa50e256ee3615697e818272064 (MD5)
Previous issue date: 2002-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
n-ary Quantum Information Defined by State Partitions
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
184karl.pdf
application/pdf
69224
https://researchspace.auckland.ac.nz/bitstream/2292/3692/1/184karl.pdf
ce95daa50e256ee3615697e818272064
MD5
1
TEXT
184karl.pdf.txt
184karl.pdf.txt
text/plain
23268
https://researchspace.auckland.ac.nz/bitstream/2292/3692/2/184karl.pdf.txt
d514ffff71a3d9aa8e5fa643a09d2f9c
MD5
2
2292/3692
oai:researchspace.auckland.ac.nz:2292/3692
2012-02-03 12:23:17.352
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3748
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Calude, C.S
Juergensen, H
2009-04-16T23:11:36Z
2009-04-16T23:11:36Z
2004-06
CDMTCS Research Reports CDMTCS-241 (2004)
1178-3540
http://hdl.handle.net/2292/3748
In this paper we prove Chaitin’s “heuristic principle”, the theorems of a finitelyspecified
theory cannot be significantly more complex than the theory itself, for an appropriate
measure of complexity. We show that the measure is invariant under the change
of the G¨odel numbering. For this measure, the theorems of a finitely-specified, sound,
consistent theory strong enough to formalize arithmetic which is arithmetically sound
(like Zermelo-Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity,
hence every sentence of the theory which is significantly more complex than the
theory is unprovable. Previous results showing that incompleteness is not accidental, but
ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence
of length n is provable in the theory tends to zero when n tends to infinity, while the
probability that a sentence of length n is true is strictly positive.
Made available in DSpace on 2009-04-16T23:11:36Z (GMT). No. of bitstreams: 1
241cris.pdf: 672303 bytes, checksum: 17476e8ac82740c99c075656aa634b89 (MD5)
Previous issue date: 2004-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Is Complexity a Source of Incompleteness?
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
241cris.pdf
application/pdf
672303
https://researchspace.auckland.ac.nz/bitstream/2292/3748/1/241cris.pdf
17476e8ac82740c99c075656aa634b89
MD5
1
TEXT
241cris.pdf.txt
241cris.pdf.txt
text/plain
41278
https://researchspace.auckland.ac.nz/bitstream/2292/3748/2/241cris.pdf.txt
a74cab82863419cb90c2dd133c64283a
MD5
2
2292/3748
oai:researchspace.auckland.ac.nz:2292/3748
2012-02-03 12:23:17.668
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3597
2020-03-09T01:54:14Z
com_2292_122
col_2292_3508
Staiger, L
2009-04-16T23:11:38Z
2009-04-16T23:11:38Z
1998-08
CDMTCS Research Reports CDMTCS-088 (1998)
1178-3540
http://hdl.handle.net/2292/3597
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.
Made available in DSpace on 2009-04-16T23:11:38Z (GMT). No. of bitstreams: 1
088ludwig.pdf: 238416 bytes, checksum: 5f42f66a0eda30e954d703ecd669765b (MD5)
Previous issue date: 1998-08
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
33898
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
The Hausdorff Measure of Regular Omega-Languages is Computable
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
088ludwig.pdf
application/pdf
238416
https://researchspace.auckland.ac.nz/bitstream/2292/3597/1/088ludwig.pdf
5f42f66a0eda30e954d703ecd669765b
MD5
1
TEXT
088ludwig.pdf.txt
088ludwig.pdf.txt
text/plain
9946
https://researchspace.auckland.ac.nz/bitstream/2292/3597/2/088ludwig.pdf.txt
479e074df98dcac2bcf8b959d69aa90f
MD5
2
2292/3597
oai:researchspace.auckland.ac.nz:2292/3597
2020-03-09 14:54:14.696
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3594
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Denny, P.C
2009-04-16T23:11:39Z
2009-04-16T23:11:39Z
1998-05
CDMTCS Research Reports CDMTCS-085 (1998)
1178-3540
http://hdl.handle.net/2292/3594
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.
Made available in DSpace on 2009-04-16T23:11:39Z (GMT). No. of bitstreams: 1
085denny.pdf: 1282878 bytes, checksum: 0d1c4580ac12a8b1280e27ea726fb3c3 (MD5)
Previous issue date: 1998-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Search and Enumeration Techniques for Incidence Structures
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
085denny.pdf
application/pdf
1282878
https://researchspace.auckland.ac.nz/bitstream/2292/3594/1/085denny.pdf
0d1c4580ac12a8b1280e27ea726fb3c3
MD5
1
TEXT
085denny.pdf.txt
085denny.pdf.txt
text/plain
688105
https://researchspace.auckland.ac.nz/bitstream/2292/3594/2/085denny.pdf.txt
f093ea633cf9bf14eaf30334fdeea4c5
MD5
2
2292/3594
oai:researchspace.auckland.ac.nz:2292/3594
2012-02-03 12:23:15.861
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3694
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Arulanandham, J.J
2009-04-16T23:11:41Z
2009-04-16T23:11:41Z
2002-05
CDMTCS Research Reports CDMTCS-186 (2002)
1178-3540
http://hdl.handle.net/2292/3694
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.
Made available in DSpace on 2009-04-16T23:11:41Z (GMT). No. of bitstreams: 1
186joshua.pdf: 729335 bytes, checksum: b345184f4c02defd65e8c59207b1b08e (MD5)
Previous issue date: 2002-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Implementing Bead--Sort with P systems
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
186joshua.pdf
application/pdf
729335
https://researchspace.auckland.ac.nz/bitstream/2292/3694/1/186joshua.pdf
b345184f4c02defd65e8c59207b1b08e
MD5
1
TEXT
186joshua.pdf.txt
186joshua.pdf.txt
text/plain
68867
https://researchspace.auckland.ac.nz/bitstream/2292/3694/2/186joshua.pdf.txt
10c4d1c46dda5d4e57f16d7c18061264
MD5
2
2292/3694
oai:researchspace.auckland.ac.nz:2292/3694
2012-02-03 12:23:13.812
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3572
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
Priese, L
Staiger, L
2009-04-16T23:11:42Z
2009-04-16T23:11:42Z
1997-10
CDMTCS Research Reports CDMTCS-063 (1997)
1178-3540
http://hdl.handle.net/2292/3572
Following Jürgensen and Thierrin [21] we say that an infinite sequence is disjunctive
if it contains any (finite) word, or, equivalently, if any word appears in the
sequence infinitely many times. “Disjunctivity” is a natural qualitative property; it is
weaker, than the property of “normality” (introduced by Borel [1]; see, for instance,
Kuipers, Niederreiter [24]). The aim of this paper is to survey some basic results
on disjunctive sequences and to explore their role in various areas of mathematics
(e.g. in automata-theoretic studies of ω-languages or number theory). To achieve
our goal we will use various instruments borrowed from topology, measure-theory,
probability theory, number theory, automata and formal languages.
Made available in DSpace on 2009-04-16T23:11:42Z (GMT). No. of bitstreams: 1
063cris.pdf: 900594 bytes, checksum: acf04399d31b54a5bfad958c68088969 (MD5)
Previous issue date: 1997-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Disjunctive Sequences: An Overview
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
063cris.pdf
application/pdf
900594
https://researchspace.auckland.ac.nz/bitstream/2292/3572/1/063cris.pdf
acf04399d31b54a5bfad958c68088969
MD5
1
TEXT
063cris.pdf.txt
063cris.pdf.txt
text/plain
87678
https://researchspace.auckland.ac.nz/bitstream/2292/3572/2/063cris.pdf.txt
db7d5069df04f9946b62a2ae50dc15cf
MD5
2
2292/3572
oai:researchspace.auckland.ac.nz:2292/3572
2012-02-03 12:23:13.447
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3689
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Khoussainov, B
Kowalski, T
2009-04-16T23:11:44Z
2009-04-16T23:11:44Z
2002-03
CDMTCS Research Reports CDMTCS-181 (2002)
1178-3540
http://hdl.handle.net/2292/3689
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.
Made available in DSpace on 2009-04-16T23:11:44Z (GMT). No. of bitstreams: 1
181bmk.pdf: 133965 bytes, checksum: bf3e4f823c71bcc0ec3adc4d07bdcca6 (MD5)
Previous issue date: 2002-03
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Computable Isomorphism of Boolean Algebras with Operators
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
181bmk.pdf
application/pdf
133965
https://researchspace.auckland.ac.nz/bitstream/2292/3689/1/181bmk.pdf
bf3e4f823c71bcc0ec3adc4d07bdcca6
MD5
1
TEXT
181bmk.pdf.txt
181bmk.pdf.txt
text/plain
21713
https://researchspace.auckland.ac.nz/bitstream/2292/3689/2/181bmk.pdf.txt
49ebdcbccdf93fe94190bd838e227805
MD5
2
2292/3689
oai:researchspace.auckland.ac.nz:2292/3689
2012-02-03 12:23:13.398
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3526
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Khoussainov, B
2009-04-16T23:11:45Z
2009-04-16T23:11:45Z
1996-08
CDMTCS Research Reports CDMTCS-017 (1996)
1178-3540
http://hdl.handle.net/2292/3526
[no abstract available]
Made available in DSpace on 2009-04-16T23:11:45Z (GMT). No. of bitstreams: 1
017bmk.pdf: 481867 bytes, checksum: bd2e8e5869308b89ba0312cd26ced520 (MD5)
Previous issue date: 1996-08
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Randomness, Computability, and Algebraic Specifications
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
017bmk.pdf
application/pdf
481867
https://researchspace.auckland.ac.nz/bitstream/2292/3526/1/017bmk.pdf
bd2e8e5869308b89ba0312cd26ced520
MD5
1
TEXT
017bmk.pdf.txt
017bmk.pdf.txt
text/plain
34612
https://researchspace.auckland.ac.nz/bitstream/2292/3526/2/017bmk.pdf.txt
4684fa716be04de9bf8097b59a42b344
MD5
2
2292/3526
oai:researchspace.auckland.ac.nz:2292/3526
2012-02-03 12:23:14.739
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3725
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
Staiger, L
2009-04-16T23:11:47Z
2009-04-16T23:11:47Z
2003-06
CDMTCS Research Reports CDMTCS-218 (2003)
1178-3540
http://hdl.handle.net/2292/3725
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.
Made available in DSpace on 2009-04-16T23:11:47Z (GMT). No. of bitstreams: 1
218cris.pdf: 227477 bytes, checksum: 4670853086f1716d424d00a297efb998 (MD5)
Previous issue date: 2003-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Generalisations of Disjunctive Sequences
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
218cris.pdf
application/pdf
227477
https://researchspace.auckland.ac.nz/bitstream/2292/3725/1/218cris.pdf
4670853086f1716d424d00a297efb998
MD5
1
TEXT
218cris.pdf.txt
218cris.pdf.txt
text/plain
27372
https://researchspace.auckland.ac.nz/bitstream/2292/3725/2/218cris.pdf.txt
dfdb7228771287376167b53c8725f6d0
MD5
2
2292/3725
oai:researchspace.auckland.ac.nz:2292/3725
2012-02-03 12:23:15.313
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3639
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Calude, C.S
Dinneen, Michael
Svozil, K
2009-04-16T23:11:48Z
2009-04-16T23:11:48Z
2000-03
CDMTCS Research Reports CDMTCS-130 (2000)
1178-3540
http://hdl.handle.net/2292/3639
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?
Made available in DSpace on 2009-04-16T23:11:48Z (GMT). No. of bitstreams: 1
130cris.pdf: 467566 bytes, checksum: bce2c383fbacefb79424b090663c5c95 (MD5)
Previous issue date: 2000-03
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Reflections on Quantum Computing
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
130cris.pdf
application/pdf
467566
https://researchspace.auckland.ac.nz/bitstream/2292/3639/1/130cris.pdf
bce2c383fbacefb79424b090663c5c95
MD5
1
TEXT
130cris.pdf.txt
130cris.pdf.txt
text/plain
14415
https://researchspace.auckland.ac.nz/bitstream/2292/3639/2/130cris.pdf.txt
c80e85cabfa69d6d37706a052c90fdc8
MD5
2
2292/3639
oai:researchspace.auckland.ac.nz:2292/3639
2012-02-03 12:23:17.468
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3687
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Svozil, K
2009-04-16T23:11:49Z
2009-04-16T23:11:49Z
2002-02
CDMTCS Research Reports CDMTCS-179 (2002)
1178-3540
http://hdl.handle.net/2292/3687
To every generalized urn model there exists a finite (Mealy) automaton with identical
propositional calculus. The converse is true as well.
Made available in DSpace on 2009-04-16T23:11:49Z (GMT). No. of bitstreams: 1
179karl.pdf: 56747 bytes, checksum: 84d9d1d8d52c5f0f103c18122e5f2dbd (MD5)
Previous issue date: 2002-02
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Logical Equivalence Between Generalized Urn Models and Finite Automata
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
179karl.pdf
application/pdf
56747
https://researchspace.auckland.ac.nz/bitstream/2292/3687/1/179karl.pdf
84d9d1d8d52c5f0f103c18122e5f2dbd
MD5
1
TEXT
179karl.pdf.txt
179karl.pdf.txt
text/plain
20327
https://researchspace.auckland.ac.nz/bitstream/2292/3687/2/179karl.pdf.txt
267073ae45661d40983ad6bbe182be98
MD5
2
2292/3687
oai:researchspace.auckland.ac.nz:2292/3687
2012-02-03 12:23:17.703
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3565
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Bridges, D.S
Dediu, L.S
2009-04-16T23:11:51Z
2009-04-16T23:11:51Z
1997-09
CDMTCS Research Reports CDMTCS-056 (1997)
1178-3540
http://hdl.handle.net/2292/3565
This paper outlines some of the history and philosophy of constructive mathematics, concentrating on the work of the late Errett Bishop and his followers.
Made available in DSpace on 2009-04-16T23:11:51Z (GMT). No. of bitstreams: 1
056douglas.pdf: 466346 bytes, checksum: bd2e2be279c0ff3196b630d2bafdb791 (MD5)
Previous issue date: 1997-09
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Paradise Lost, or Paradise Regained?
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
056douglas.pdf
application/pdf
466346
https://researchspace.auckland.ac.nz/bitstream/2292/3565/1/056douglas.pdf
bd2e2be279c0ff3196b630d2bafdb791
MD5
1
TEXT
056douglas.pdf.txt
056douglas.pdf.txt
text/plain
85365
https://researchspace.auckland.ac.nz/bitstream/2292/3565/2/056douglas.pdf.txt
ecd93e8094e24d0c7b6911757c017d1d
MD5
2
2292/3565
oai:researchspace.auckland.ac.nz:2292/3565
2012-02-03 12:23:16.601
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3540
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Khoussainov, B
Shore, R.A
2009-04-16T23:11:52Z
2009-04-16T23:11:52Z
1997-04
CDMTCS Research Reports CDMTCS-031 (1997)
1178-3540
http://hdl.handle.net/2292/3540
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.
Made available in DSpace on 2009-04-16T23:11:52Z (GMT). No. of bitstreams: 1
031bmk.pdf: 454685 bytes, checksum: 39dbe31d12dc61e459153afb418d2509 (MD5)
Previous issue date: 1997-04
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Computable Isomorphisms, Degree Spectra of Relations, and Scott Families
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
031bmk.pdf
application/pdf
454685
https://researchspace.auckland.ac.nz/bitstream/2292/3540/1/031bmk.pdf
39dbe31d12dc61e459153afb418d2509
MD5
1
TEXT
031bmk.pdf.txt
031bmk.pdf.txt
text/plain
117786
https://researchspace.auckland.ac.nz/bitstream/2292/3540/2/031bmk.pdf.txt
a58e4045bd74310b5ccac773476b401a
MD5
2
2292/3540
oai:researchspace.auckland.ac.nz:2292/3540
2012-02-03 12:23:13.541
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3668
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Meyerstein, F.W
Moller, A.P
2009-04-16T23:11:54Z
2009-04-16T23:11:54Z
2001-09
CDMTCS Research Reports CDMTCS-160 (2001)
1178-3540
http://hdl.handle.net/2292/3668
[no abstract available]
Made available in DSpace on 2009-04-16T23:11:54Z (GMT). No. of bitstreams: 1
160MM.pdf: 1576882 bytes, checksum: b1b50cb693d48c937e2bcdadb38a9a0b (MD5)
Previous issue date: 2001-09
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
LifeTime: A Unified Study of Life (A Preliminary Version)
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
160MM.pdf
application/pdf
1576882
https://researchspace.auckland.ac.nz/bitstream/2292/3668/1/160MM.pdf
b1b50cb693d48c937e2bcdadb38a9a0b
MD5
1
TEXT
160MM.pdf.txt
160MM.pdf.txt
text/plain
563268
https://researchspace.auckland.ac.nz/bitstream/2292/3668/2/160MM.pdf.txt
be08aa6dd99590a1f1b0755cbfa5003c
MD5
2
2292/3668
oai:researchspace.auckland.ac.nz:2292/3668
2012-02-03 12:23:17.007
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3752
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
Harmer, M.
2009-04-16T23:11:55Z
2009-04-16T23:11:55Z
2004-07
CDMTCS Research Reports CDMTCS-245 (2004)
1178-3540
http://hdl.handle.net/2292/3752
A solvable model corresponding to a given quantum network is
described in [22] without an explicit description of how to fit the parameters
of the solvable model. Here we give a procedure to fit these
parameters so that the solvable model reproduces the important features,
viz. the scattering matrix for the physically relevant energies, of
the quantum network, subject to the non-vanishing of a determinant.
Made available in DSpace on 2009-04-16T23:11:55Z (GMT). No. of bitstreams: 1
245mark.pdf: 191658 bytes, checksum: 4c1efed3e8b42f15cee5c95cb182e23f (MD5)
Previous issue date: 2004-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Fitting Parameters for a Solvable Model of a Quantum Network (CDMTCS)
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
245mark.pdf
application/pdf
191658
https://researchspace.auckland.ac.nz/bitstream/2292/3752/1/245mark.pdf
4c1efed3e8b42f15cee5c95cb182e23f
MD5
1
TEXT
245mark.pdf.txt
245mark.pdf.txt
text/plain
16919
https://researchspace.auckland.ac.nz/bitstream/2292/3752/2/245mark.pdf.txt
fcedfbd71e484c20d424885ec3b28960
MD5
2
2292/3752
oai:researchspace.auckland.ac.nz:2292/3752
2012-02-03 12:23:19.535
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3611
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
Paun, G
2009-04-16T23:11:57Z
2009-04-16T23:11:57Z
1999-05
CDMTCS Research Reports CDMTCS-102 (1999)
1178-3540
http://hdl.handle.net/2292/3611
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.
Made available in DSpace on 2009-04-16T23:11:57Z (GMT). No. of bitstreams: 1
102paun.pdf: 277948 bytes, checksum: 401eb719cde471569eedddcdc6e4d8b5 (MD5)
Previous issue date: 1999-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
P Systems with Active Membranes: Attacking NP Complete Problems
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
102paun.pdf
application/pdf
277948
https://researchspace.auckland.ac.nz/bitstream/2292/3611/1/102paun.pdf
401eb719cde471569eedddcdc6e4d8b5
MD5
1
TEXT
102paun.pdf.txt
102paun.pdf.txt
text/plain
42225
https://researchspace.auckland.ac.nz/bitstream/2292/3611/2/102paun.pdf.txt
5c3e185de3bf229d00d96b00a6be6ce6
MD5
2
2292/3611
oai:researchspace.auckland.ac.nz:2292/3611
2012-02-03 12:23:16.584
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3715
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Khoussainov, B
Rubin, S
Stephan, F
2009-04-16T23:11:58Z
2009-04-16T23:11:58Z
2003-11
CDMTCS Research Reports CDMTCS-208 (2003)
1178-3540
http://hdl.handle.net/2292/3715
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.
Made available in DSpace on 2009-04-16T23:11:58Z (GMT). No. of bitstreams: 1
208rubin.pdf: 452665 bytes, checksum: c6ea71abcdf06e639c6fcc038e715312 (MD5)
Previous issue date: 2003-11
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Automatic linear orders and trees (Revised)
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
208rubin.pdf
application/pdf
452665
https://researchspace.auckland.ac.nz/bitstream/2292/3715/1/208rubin.pdf
c6ea71abcdf06e639c6fcc038e715312
MD5
1
TEXT
208rubin.pdf.txt
208rubin.pdf.txt
text/plain
312275
https://researchspace.auckland.ac.nz/bitstream/2292/3715/2/208rubin.pdf.txt
e20eb9da8290cc9325a347b8c6285958
MD5
2
2292/3715
oai:researchspace.auckland.ac.nz:2292/3715
2012-02-03 12:23:13.51
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3681
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
Downey, R.G
2009-04-16T23:12:00Z
2009-04-16T23:12:00Z
2002-01
CDMTCS Research Reports CDMTCS-173 (2002)
1178-3540
http://hdl.handle.net/2292/3681
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.
Made available in DSpace on 2009-04-16T23:12:00Z (GMT). No. of bitstreams: 1
173rod.pdf: 523091 bytes, checksum: 1ae1d95ab16e437cd959acdcc8a71c0c (MD5)
Previous issue date: 2002-01
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Some Computability-Theoretical Aspects of Reals and Randomness
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
173rod.pdf
application/pdf
523091
https://researchspace.auckland.ac.nz/bitstream/2292/3681/1/173rod.pdf
1ae1d95ab16e437cd959acdcc8a71c0c
MD5
1
TEXT
173rod.pdf.txt
173rod.pdf.txt
text/plain
208854
https://researchspace.auckland.ac.nz/bitstream/2292/3681/2/173rod.pdf.txt
db954cfd53173493191a1a7b8e1db8ab
MD5
2
2292/3681
oai:researchspace.auckland.ac.nz:2292/3681
2012-02-03 12:23:17.159
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3726
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Calude, C.S
2009-04-16T23:12:01Z
2009-04-16T23:12:01Z
2003-06
CDMTCS Research Reports CDMTCS-219 (2003)
1178-3540
http://hdl.handle.net/2292/3726
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.
Made available in DSpace on 2009-04-16T23:12:01Z (GMT). No. of bitstreams: 1
219cris.pdf: 137514 bytes, checksum: 71981ad6b3677bdc703ccc2a309ab5fd (MD5)
Previous issue date: 2003-06
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Dialogues on Quantum Computing
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
219cris.pdf
application/pdf
137514
https://researchspace.auckland.ac.nz/bitstream/2292/3726/1/219cris.pdf
71981ad6b3677bdc703ccc2a309ab5fd
MD5
1
TEXT
219cris.pdf.txt
219cris.pdf.txt
text/plain
30327
https://researchspace.auckland.ac.nz/bitstream/2292/3726/2/219cris.pdf.txt
d5a67f62e7d88de3cfc990b167793d13
MD5
2
2292/3726
oai:researchspace.auckland.ac.nz:2292/3726
2012-02-03 12:23:13.595
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3578
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Bridges, D.S
Richman, F
Schuster, P
2009-04-16T23:12:02Z
2009-04-16T23:12:02Z
1997-11
CDMTCS Research Reports CDMTCS-069 (1997)
1178-3540
http://hdl.handle.net/2292/3578
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.
Made available in DSpace on 2009-04-16T23:12:02Z (GMT). No. of bitstreams: 1
069douglas.pdf: 579739 bytes, checksum: cb17b7da499fe7f29d7e91390825b252 (MD5)
Previous issue date: 1997-11
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Adjoints, Absolute Values and Polar Decompostions
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
069douglas.pdf
application/pdf
579739
https://researchspace.auckland.ac.nz/bitstream/2292/3578/1/069douglas.pdf
cb17b7da499fe7f29d7e91390825b252
MD5
1
TEXT
069douglas.pdf.txt
069douglas.pdf.txt
text/plain
22809
https://researchspace.auckland.ac.nz/bitstream/2292/3578/2/069douglas.pdf.txt
07e95987fb48bc0b85d75c97eca6d50e
MD5
2
2292/3578
oai:researchspace.auckland.ac.nz:2292/3578
2012-02-03 12:23:13.495
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3612
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Assanovich, B
Gunther, Ulrich
2009-04-16T23:12:04Z
2009-04-16T23:12:04Z
1999-05
CDMTCS Research Reports CDMTCS-103 (1999)
1178-3540
http://hdl.handle.net/2292/3612
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.
Made available in DSpace on 2009-04-16T23:12:04Z (GMT). No. of bitstreams: 1
103boris.pdf: 209537 bytes, checksum: 31efaf44b607be5ef67273482e127240 (MD5)
Previous issue date: 1999-05
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Variable-Length Codes for Sources with Equiprobable Symbols
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
103boris.pdf
application/pdf
209537
https://researchspace.auckland.ac.nz/bitstream/2292/3612/1/103boris.pdf
31efaf44b607be5ef67273482e127240
MD5
1
TEXT
103boris.pdf.txt
103boris.pdf.txt
text/plain
14710
https://researchspace.auckland.ac.nz/bitstream/2292/3612/2/103boris.pdf.txt
7a3ba63f197fd3cc49b46f028958f319
MD5
2
2292/3612
oai:researchspace.auckland.ac.nz:2292/3612
2012-02-03 12:23:13.48
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3621
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
Juergensen, H
Legg, S
2009-04-16T23:12:06Z
2009-04-16T23:12:06Z
1999-09
CDMTCS Research Reports CDMTCS-112 (1999)
1178-3540
http://hdl.handle.net/2292/3621
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.
Made available in DSpace on 2009-04-16T23:12:06Z (GMT). No. of bitstreams: 1
112cris.pdf: 192729 bytes, checksum: 87ff0864536ffd04d7d8a61f78483dde (MD5)
Previous issue date: 1999-09
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Solving Problems with Finite Test Sets
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
112cris.pdf
application/pdf
192729
https://researchspace.auckland.ac.nz/bitstream/2292/3621/1/112cris.pdf
87ff0864536ffd04d7d8a61f78483dde
MD5
1
TEXT
112cris.pdf.txt
112cris.pdf.txt
text/plain
26811
https://researchspace.auckland.ac.nz/bitstream/2292/3621/2/112cris.pdf.txt
5299e1ccbfdacdb936990fb1e1d90f42
MD5
2
2292/3621
oai:researchspace.auckland.ac.nz:2292/3621
2012-02-03 12:23:15.875
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3821
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
Goles, E
Littleland, Cedric
Rapaport, I
2009-04-16T23:12:07Z
2009-04-16T23:12:07Z
2007-11
CDMTCS Research Reports CDMTCS-314 (2007)
1178-3540
http://hdl.handle.net/2292/3821
Made available in DSpace on 2009-04-16T23:12:07Z (GMT). No. of bitstreams: 1
314eric.pdf: 277636 bytes, checksum: 87c047da450434fd72a4959ca8373e17 (MD5)
Previous issue date: 2007-11
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
The Underlying Optimal Protocol of Rule 218 Cellular Automaton
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
314eric.pdf
application/pdf
277636
https://researchspace.auckland.ac.nz/bitstream/2292/3821/1/314eric.pdf
87c047da450434fd72a4959ca8373e17
MD5
1
TEXT
314eric.pdf.txt
314eric.pdf.txt
text/plain
17559
https://researchspace.auckland.ac.nz/bitstream/2292/3821/2/314eric.pdf.txt
94dab78646710e9bee8b2472554cfe50
MD5
2
2292/3821
oai:researchspace.auckland.ac.nz:2292/3821
2012-02-03 12:23:13.662
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3740
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Svozil, K
2009-04-16T23:12:09Z
2009-04-16T23:12:09Z
2004-01
CDMTCS Research Reports CDMTCS-233 (2004)
1178-3540
http://hdl.handle.net/2292/3740
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.
Made available in DSpace on 2009-04-16T23:12:09Z (GMT). No. of bitstreams: 1
233karl.pdf: 80078 bytes, checksum: f72844c3baba126470a85ffbcdcf4da5 (MD5)
Previous issue date: 2004-01
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Quantum Information via State Partitions and the Context Transition Principle
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
233karl.pdf
application/pdf
80078
https://researchspace.auckland.ac.nz/bitstream/2292/3740/1/233karl.pdf
f72844c3baba126470a85ffbcdcf4da5
MD5
1
TEXT
233karl.pdf.txt
233karl.pdf.txt
text/plain
25859
https://researchspace.auckland.ac.nz/bitstream/2292/3740/2/233karl.pdf.txt
26c25595d057bf88e2efb69e7bf8abfc
MD5
2
2292/3740
oai:researchspace.auckland.ac.nz:2292/3740
2012-02-03 12:23:15.051
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3528
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
Dinneen, Michael
Cattell, K
Fellows, M.R
2009-04-16T23:12:10Z
2009-04-16T23:12:10Z
1996-10
CDMTCS Research Reports CDMTCS-019 (1996)
1178-3540
http://hdl.handle.net/2292/3528
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.
Made available in DSpace on 2009-04-16T23:12:10Z (GMT). No. of bitstreams: 1
019mjd.pdf: 686268 bytes, checksum: 2da18c5bd6fd8a79aa1c0f811c90ddf8 (MD5)
Previous issue date: 1996-10
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Forbidden Minors to Graphs with Small Feedback Sets
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
019mjd.pdf
application/pdf
686268
https://researchspace.auckland.ac.nz/bitstream/2292/3528/1/019mjd.pdf
2da18c5bd6fd8a79aa1c0f811c90ddf8
MD5
1
TEXT
019mjd.pdf.txt
019mjd.pdf.txt
text/plain
80520
https://researchspace.auckland.ac.nz/bitstream/2292/3528/2/019mjd.pdf.txt
ae35ca3ff3d007346a9833244bc1b37e
MD5
2
2292/3528
oai:researchspace.auckland.ac.nz:2292/3528
2012-02-03 12:23:14.2
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3835
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Calude, C.S
Hay, N.J
2009-04-16T23:12:12Z
2009-04-16T23:12:12Z
2008-07
CDMTCS Research Reports CDMTCS-328 (2008)
1178-3540
http://hdl.handle.net/2292/3835
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.
Made available in DSpace on 2009-04-16T23:12:12Z (GMT). No. of bitstreams: 1
328cris.pdf: 394959 bytes, checksum: 79b5a2799a3c187dc79777dbbc4f04ec (MD5)
Previous issue date: 2008-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Every Computably Enumerable Random Real Is Provably Computably Enumerable Random
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
328cris.pdf
application/pdf
394959
https://researchspace.auckland.ac.nz/bitstream/2292/3835/1/328cris.pdf
79b5a2799a3c187dc79777dbbc4f04ec
MD5
1
TEXT
328cris.pdf.txt
328cris.pdf.txt
text/plain
52335
https://researchspace.auckland.ac.nz/bitstream/2292/3835/2/328cris.pdf.txt
6cf2705161a9af9e381c9b39adcb12e6
MD5
2
2292/3835
oai:researchspace.auckland.ac.nz:2292/3835
2012-02-03 12:23:15.294
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3836
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
Dinneen, Michael
Fenton, A.J.L
2009-04-16T23:12:13Z
2009-04-16T23:12:13Z
2008-07
CDMTCS Research Reports CDMTCS-329 (2008)
1178-3540
http://hdl.handle.net/2292/3836
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.
Made available in DSpace on 2009-04-16T23:12:13Z (GMT). No. of bitstreams: 1
329mjd.pdf: 406721 bytes, checksum: 913bac25fdb7e910be26adfa6d3e3c74 (MD5)
Previous issue date: 2008-07
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
A New Linear-Time Dominating Number Algorithm for Graphs of Bounded Pathwidth
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
329mjd.pdf
application/pdf
406721
https://researchspace.auckland.ac.nz/bitstream/2292/3836/1/329mjd.pdf
913bac25fdb7e910be26adfa6d3e3c74
MD5
1
TEXT
329mjd.pdf.txt
329mjd.pdf.txt
text/plain
33831
https://researchspace.auckland.ac.nz/bitstream/2292/3836/2/329mjd.pdf.txt
5a176fd76a203645bb3587596f704e66
MD5
2
2292/3836
oai:researchspace.auckland.ac.nz:2292/3836
2012-02-03 12:23:19.369
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
oai:researchspace.auckland.ac.nz:2292/3805
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
Staiger, L
2009-04-16T23:12:15Z
2009-04-16T23:12:15Z
2007-01
CDMTCS Research Reports CDMTCS-298 (2007)
1178-3540
http://hdl.handle.net/2292/3805
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.
Made available in DSpace on 2009-04-16T23:12:15Z (GMT). No. of bitstreams: 1
298ludwig.pdf: 141952 bytes, checksum: bcabf0b15166f12d2177f181aa7a31f8 (MD5)
Previous issue date: 2007-01
Department of Computer Science, The University of Auckland, New Zealand
CDMTCS Research Report Series
https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm
The author(s)
http://purl.org/eprint/accessRights/OpenAccess
http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial
Prefix-free Lukasiewicz Languages
Technical Report
Fields of Research::280000 Information, Computing and Communication Sciences
ORIGINAL
298ludwig.pdf
application/pdf
141952
https://researchspace.auckland.ac.nz/bitstream/2292/3805/1/298ludwig.pdf
bcabf0b15166f12d2177f181aa7a31f8
MD5
1
TEXT
298ludwig.pdf.txt
298ludwig.pdf.txt
text/plain
16504
https://researchspace.auckland.ac.nz/bitstream/2292/3805/2/298ludwig.pdf.txt
38011bebc40102009de99aa481428a49
MD5
2
2292/3805
oai:researchspace.auckland.ac.nz:2292/3805
2012-02-03 12:23:15.764
ResearchSpace 3.2 at The University of Auckland
researchspace@auckland.ac.nz
MToxMDB8Mjpjb2xfMjI5Ml8zNTA4fDM6fDQ6fDU6eG9haQ==