2020-07-11T12:43:48Z
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
ResearchSpace 3.2 at The University of Auckland
author
Gibbons, Jenny
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.
An initial-algebra approach to directed acyclic graphs
Technical Report
TGljZW5zZSBncmFudGVkIGJ5IFZhbmVzc2EgTmV3dG9uLVdhZGUgKHYubmV3dG9uLXdhZGVAYXVja2xhbmQuYWMubnopIG9uIDIwMDktMDQtMTRUMjM6MDY6MThaIChHTVQpOgoKPHA+RGVwb3NpdCBMaWNlbmNlIC0gU3VtbWFyeSAtIFJlc2VhcmNoU3BhY2U8L3A+CjxwPlN1bW1hcnkgb2YgRGVwb3NpdCBMaWNlbmNlIGZvciBUaGUgVW5pdmVyc2l0eSBvZiBBdWNrbGFuZCBMaWJyYXJ5J3MKZGlnaXRhbCByZXBvc2l0b3J5IGZvciByZXNlYXJjaCBjdXJyZW50bHkgY2FsbGVkIFJlc2VhcmNoU3BhY2UgYW5kCmxvY2F0ZWQgYXQgd3d3LnJlc2VhcmNoc3BhY2UuYXVja2xhbmQuYWMubnoKPC9wPjxwPgpXb3JrIGRlcG9zaXRlZCBhbmQgc3RvcmVkIGluIFJlc2VhcmNoU3BhY2UgaXMgcmVzdHJpY3RlZCB0byBSZXNlYXJjaApPdXRwdXRzIGNyZWF0ZWQgYnkgbWVtYmVycyBvZiBUaGUgVW5pdmVyc2l0eSBvZiBBdWNrbGFuZCwgaW5jbHVkaW5nIApqb3VybmFsIGFydGljbGVzLCBjb25mZXJlbmNlIHBhcGVycywgcmVzZWFyY2gvdGVjaG5pY2FsIHJlcG9ydHMsIG9yCm90aGVyIHJlc2VhcmNoIG1hdGVyaWFscy4KPC9wPjxwPllvdXIgcmlnaHRzIGFuZCBDb25kaXRpb25zIG9mIERlcG9zaXQKPC9wPjxwPkJ5IGRlcG9zaXRpbmcgdGhlIFdvcmsgaW4gVGhlIFVuaXZlcnNpdHkgb2YgQXVja2xhbmQgTGlicmFyeSdzCmRpZ2l0YWwgcmVwb3NpdG9yeSBmb3IgcmVzZWFyY2gsIFJlc2VhY2hTcGFjZSwgSSBncmFudCBUaGUgVW5pdmVyc2l0eQpvZiBBdWNrbGFuZCBhIG5vbi1leGNsdXNpdmUgbGljZW5jZSB0byBjb3B5LCB0cmFuc2xhdGUgdG8gYW55IG1lZGl1bQpvciBmb3JtYXQgKGZvciB0aGUgcHVycG9zZSBvZiBwcmVzZXJ2YXRpb24gb3IgbWlncmF0aW9uKSwgYW5kL29yCmNvbW11bmljYXRlIHRoZSBXb3JrIChpbmNsdWRpbmcgdGhlIGFic3RyYWN0KSB3b3JsZHdpZGUgaW4gZWxlY3Ryb25pYwpmb3JtYXQgaW4gYWNjb3JkYW5jZSB3aXRoIHRoZSB0ZXJtcyBhbmQgY29uZGl0aW9ucyBvZiB0aGUgRnVsbCBEZXBvc2l0CkxpY2VuY2UgYW5kIHRoZSBVbml2ZXJzaXR5J3MgSW50ZWxsZWN0dWFsIFByb3BlcnR5IEluY2x1ZGluZyAKbnZlbnRpb25zIGFuZCBQYXRlbnRzIFBvbGljeS4KPC9wPjxwPkluIGdyYW50aW5nIHRoZSBsaWNlbmNlIEkgdW5kZXJzdGFuZCB0aGF0Ogo8L3A+PHA+KiBJIGFtIGZyZWUgdG8gcHVibGlzaCB0aGUgV29yayBpbiBpdHMgcHJlc2VudCB2ZXJzaW9uIG9yCmZ1dHVyZSB2ZXJzaW9ucyBlbHNld2hlcmUsIGFuZCBubyBvd25lcnNoaXAgaXMgYXNzdW1lZCBieSAKVGhlIFVuaXZlcnNpdHkgb2YgQXVja2xhbmQgTGlicmFyeSB3aGVuIHN0b3JpbmcgYSBkaWdpdGFsIGNvcHkgb2YgCnRoZSBXb3JrOwoqIElmIGNvcHlyaWdodCBoYXMgYWxyZWFkeSBiZWVuIHRyYW5zZmVycmVkIHRvIGEgcHVibGlzaGVyLApSZXNlYXJjaFNwYWNlIEFkbWluaXN0cmF0b3JzIHdpbGwgb25seSBjb21tdW5pY2F0ZSBvciBtYWtlIGF2YWlsYWJsZQp0aGUgV29yayBpbiBhY2NvcmRhbmNlIHdpdGggdGhlIHB1Ymxpc2hlcidzIGNvcHlyaWdodCBjb25kaXRpb25zOwoqIE9uY2UgdGhlIFdvcmsgaXMgdXBsb2FkZWQgdG8gUmVzZWFyY2hTcGFjZSBhIGNpdGF0aW9uIHdpbGwgCmFsd2F5cyByZW1haW4gdmlzaWJsZSBhbHRob3VnaCBhcyB0aGUgY29weXJpZ2h0IG93bmVyLCBvciB3aXRoIHRoZQpleHByZXNzIGF1dGhvcmlzYXRpb24gb2YgdGhlIGNvcHlyaWdodCBvd25lciwgSSB3aWxsIHJldGFpbiB0aGUgcmlnaHQKdG8gdXBkYXRlIGl0OwoqIFJlc2VhcmNoU3BhY2UgQWRtaW5pc3RyYXRvcnMgbWF5IGtlZXAgbW9yZSB0aGFuIG9uZSBjb3B5IG9mIHRoZQpXb3JrIGZvciBwdXJwb3NlcyBvZiBzZWN1cml0eSwgYmFjay11cCBhbmQgcHJlc2VydmF0aW9uOwoqIEkgbWF5IHJlbW92ZSB0aGUgV29yayBmcm9tIFJlc2VhcmNoU3BhY2UgYW5kIHRoYXQgdGhpcyBwcm9jZXNzIG1heQp0YWtlIHVwIHRvIGZpdmUgd29ya2luZyBkYXlzOwoqIFRoZSBVbml2ZXJzaXR5IG9mIEF1Y2tsYW5kIExpYnJhcnkgbWF5IHJlbW92ZSB0aGUgV29yayBmcm9tIApSZXNlYXJjaFNwYWNlIHdpdGhvdXQgbm90aWNlIGZvciBwcm9mZXNzaW9uYWwsIGxlZ2FsIG9yIGFkbWluaXN0cmF0aXZlCnJlYXNvbnMuPC9wPgo8cD5JIEFncmVlIGFzIGZvbGxvd3M6PC9wPgo8cD4qIEkgaGF2ZSB0aGUgYXV0aG9yaXR5IHRvIG1ha2UgdGhpcyBhZ3JlZW1lbnQgYXMgY29weXJpZ2h0IG93bmVyLCAKb3Igd2l0aCB0aGUgZXhwcmVzcyBhdXRob3Jpc2F0aW9uIG9mIHRoZSBjb3B5cmlnaHQgb3duZXIsIGFuZCBoZXJlYnkKZ2l2ZSBUaGUgVW5pdmVyc2l0eSBvZiBBdWNrbGFuZCBMaWJyYXJ5J3MgUmVzZWFyY2hTcGFjZSBBZG1pbmlzdHJhdG9ycwp0aGUgcmlnaHQgdG8gbWFrZSB0aGUgV29yayBhdmFpbGFibGUgaW4gdGhlIHdheSBkZXNjcmliZWQgYWJvdmUuCiogVGhlIFdvcmsgZG9lcyBub3QgYnJlYWNoIHRoZSBwcml2YWN5IG9mIGFueSB0aGlyZCBwYXJ0eSBvciBjb250YWluCmRlZmFtYXRvcnksIG9mZmVuc2l2ZSBvciB1bmxhd2Z1bCBtYXR0ZXIuCiogQWxsIGNvbnRlbnQgaGFzIGJlZW4gcHJvcGVybHkgYWNrbm93bGVkZ2VkLCBhbmQgZWl0aGVyOgooYSkgdGhlIFdvcmsgZG9lcyBub3QgaW5mcmluZ2UgdGhlIGNvcHlyaWdodCBvZiBhbnkgb3RoZXIgcGVyc29uLCBvcgooYikgSSBoYXZlIG9idGFpbmVkIHdyaXR0ZW4gcGVybWlzc2lvbiB0byB1c2UgYW55IG90aGVyIHBlcnNvbidzIApjb3B5cmlnaHQgbWF0ZXJpYWwgYW5kLCBpZiB0aGUgV29yayBpcyB1bnB1Ymxpc2hlZCwgYXR0YWNoIGNvcGllcyBvZgplYWNoIHBlcm1pc3Npb24uCiogUmVzZWFyY2hTcGFjZSBBZG1pbmlzdHJhdG9ycyBhcmUgdW5kZXIgbm8gb2JsaWdhdGlvbiB0byBkZWZlbmQgb3IKdGFrZSBsZWdhbCBhY3Rpb24gb24gbXkgYmVoYWxmLCBvciBvbiBiZWhhbGYgb2YgYW55IG90aGVyIHJpZ2h0cwpob2xkZXIocykgaWYgdGhlIFdvcmsgYnJlYWNoZXMgaW50ZWxsZWN0dWFsIHByb3BlcnR5IHJpZ2h0cywgb3IgaXMKb3RoZXJ3aXNlIHN1YmplY3QgdG8gbGVnYWwgZGlzcHV0ZS4KKiBJZiB0aGUgV29yayBpcyBiYXNlZCB1cG9uIHdvcmsgdGhhdCBoYXMgYmVlbiBzcG9uc29yZWQgb3IgZnVuZGVkIGJ5CmFuIGVudGl0eSBvdGhlciB0aGFuIFRoZSBVbml2ZXJzaXR5IG9mIEF1Y2tsYW5kLCBJIHJlcHJlc2VudCB0aGF0IEkKaGF2ZSBmdWxmaWxsZWQgYW55IHJpZ2h0IG9mIHJldmlldyBvciBvdGhlciBvYmxpZ2F0aW9uIHJlcXVpcmVkIG9mIG1lCnVuZGVyIHRoZSBjb250cmFjdCBvciBhZ3JlZW1lbnQgd2l0aCB0aGF0IGVudGl0eSBhbmQgdGhhdCB0aGUgdXNlIG9mCnRoZSBXb3JrIGFzIHNldCBvdXQgaW4gdGhpcyBsaWNlbmNlIGRvZXMgbm90IGluZnJpbmdlIHRoZSBpbnRlbGxlY3R1YWwKcHJvcGVydHkgcmlnaHRzIG9mIHRoZSBlbnRpdHkuCiogSSBoYXZlIHJlYWQgYW5kIGFncmVlIHRvIGJlIGJvdW5kIGJ5IHRoZSAgPGEgaHJlZj0iaHR0cDovL3Jlc2VhcmNoc3BhY2UuYXVja2xhbmQuYWMubnovZG9jcy91b2EtZG9jcy9kZXBvc2l0bGljZW5jZWZ1bGwuaHRtIj5GdWxsIERlcG9zaXQgTGljZW5jZTwvYT4KdGVybXMgYW5kIGNvbmRpdGlvbnMuPC9wPgo=
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3509/2/001damgs.pdf
File
MD5
85d29aa43a9a0386b6be6dc1798d07f1
239662
application/pdf
001damgs.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3509/3/001damgs.pdf.txt
File
MD5
1d7b7582e444e8f153995e9479baf7c0
47197
text/plain
001damgs.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3665
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Lee, S.Y.P
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.
A Conference Submission Web Server
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3665/1/157sophia.pdf
File
MD5
4b6a38c9c3d71ed36df1aa1e7d85457e
1007741
application/pdf
157sophia.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3665/2/157sophia.pdf.txt
File
MD5
3ffdf4f058dd8011637f93adf6a6112e
35216
text/plain
157sophia.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3747
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Automata Recognizing No Words: A Statistical Approach
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3747/1/240cris.pdf
File
MD5
3ae683a2e7dc2d56981af92cf673cf71
650900
application/pdf
240cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3747/2/240cris.pdf.txt
File
MD5
ac344be5f6d660219da356dd62d37883
38448
text/plain
240cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3727
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Arulanandham, J.J
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.
A Fast Natural Algorithm for Searching
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3727/1/220joshua.pdf
File
MD5
6276410af2469c0b5003bd4e065cfef6
151615
application/pdf
220joshua.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3727/2/220joshua.pdf.txt
File
MD5
bfb8ea3efa8a8c35c25b3a298b19f428
22091
text/plain
220joshua.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3573
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Hertling, P
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.
Surjective Functions on Computably Growing Cantor Sets
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3573/1/064hertling.pdf
File
MD5
8582807927750fd66acaf90fcadf716e
350536
application/pdf
064hertling.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3573/2/064hertling.pdf.txt
File
MD5
6b9f3e8566836f8532d86a48785d5352
40652
text/plain
064hertling.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3768
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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%.
What is the Value of Taxicab(6)? An Update
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3768/1/261cris.pdf
File
MD5
cf0087aa2e10b331f0eba3b5b0f4074b
479185
application/pdf
261cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3768/2/261cris.pdf.txt
File
MD5
890a741527b39bb448a7f273de90fa4b
12871
text/plain
261cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3627
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Dinneen, Michael
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.
The Minor-Order Obstructions for The Graphs of Vertex Cover Six
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3627/1/118vc6.pdf
File
MD5
186cfe3610980f29820ee7e28f8fd6da
411511
application/pdf
118vc6.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3627/2/118vc6.pdf.txt
File
MD5
fa6004c4a5f08c400d03963cedca88a2
48214
text/plain
118vc6.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3695
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Becher, V
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.
Another Example of Higher Order Randomness
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3695/1/187vero.pdf
File
MD5
2e57a6dfe14925f396db957499b5f3fa
192546
application/pdf
187vero.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3695/2/187vero.pdf.txt
File
MD5
c8db933707720d96b67356b73c862d0d
37735
text/plain
187vero.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3624
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Kapoulas, G
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.
Computable $p$-adic Numbers
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3624/1/115george.pdf
File
MD5
f11da230ed90eeadc4329690218841dd
235100
application/pdf
115george.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3624/2/115george.pdf.txt
File
MD5
9ff23e4ade9dd429bbb4f65b34585637
61049
text/plain
115george.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3771
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Staiger, L
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.
Infinite Iterated Function Systems in Cantor Space and the Hausdorff Measure of omega-power Languages
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3771/1/264ludwig.pdf
File
MD5
76a7904d378935e4cd3402ca61b5fd43
254382
application/pdf
264ludwig.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3771/2/264ludwig.pdf.txt
File
MD5
3b47128f64ac7aad2b989f4f911e5f30
38126
text/plain
264ludwig.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3774
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Titchener, M.R
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.
A Comparison of Practical Information Measures
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3774/1/267titchener.pdf
File
MD5
a5ddf3fdce5f1de400c3ef8f8b00c7fe
530784
application/pdf
267titchener.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3774/2/267titchener.pdf.txt
File
MD5
ad886ad5197e7a92bbd7b5b4b6c87c06
19687
text/plain
267titchener.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3796
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Firror, G
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.
Longest Alternating Subsequences in Pattern-Restricted Permutations
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3796/1/289wilson.pdf
File
MD5
5b75658d6c0442e48db1bbbe3577362f
570072
application/pdf
289wilson.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3796/2/289wilson.pdf.txt
File
MD5
e16376c730275dcc7d67c8d8d7f4f3aa
383
text/plain
289wilson.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3793
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Speidel, U
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.
T-Complexity and T-Information Theory--an Executive Summary, 2nd revised version
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3793/1/286ulrich.pdf
File
MD5
c2cfbd1ac38f9d8b707e8e186dfacae2
140932
application/pdf
286ulrich.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3793/2/286ulrich.pdf.txt
File
MD5
c924f3e8bb6a2a42a9f01947198cee41
25140
text/plain
286ulrich.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3574
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Hertling, P
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.
Embedding Cellular Automata into Reversible Ones
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3574/1/065hertling.pdf
File
MD5
07f747b088f21b8a5b14a88c55d3dee3
270542
application/pdf
065hertling.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3574/2/065hertling.pdf.txt
File
MD5
fe162bd60eb830a9d4e7931ea1d5596e
37870
text/plain
065hertling.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3867
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Svozil, K
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.
On the Brightness of the Thomson lamp. A Prolegomenon to Quantum Recursion Theory
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3867/1/361karl.pdf
File
MD5
2d515dd7502ce3de17b9f2799dec1340
296461
application/pdf
361karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3867/2/361karl.pdf.txt
File
MD5
d22f9f7bd8e0435ed73b39880cd86fbd
32558
text/plain
361karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3792
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
De-Quantising the Solution of Deutsch's Prolem
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3792/1/285cris.pdf
File
MD5
2c24601fdb08b7348cf087e12d559fae
231689
application/pdf
285cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3792/2/285cris.pdf.txt
File
MD5
ddcf7a27656a688b089fd4f5aa1dd447
12401
text/plain
285cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3693
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Khoussainov, B
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
Some Thoughts On Automatic Structures
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3693/1/185sasha.pdf
File
MD5
96b584d0c9cdee34b4d5561148fbb8a3
190201
application/pdf
185sasha.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3693/2/185sasha.pdf.txt
File
MD5
d49637c68daf3ea2fadf3d1bf4c2aad1
37735
text/plain
185sasha.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3770
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Pemantle, R
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.
Twenty Combinatorial Examples of Asymptotics Derived From Multivariate Generating Functions
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3770/1/263mcwrap.pdf
File
MD5
37b56f375dfab459ad49e6b780f9d96f
679103
application/pdf
263mcwrap.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3770/2/263mcwrap.pdf.txt
File
MD5
ef92838b2049d6ba3dc268c105e8438a
156598
text/plain
263mcwrap.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3667
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Bridges, D.S
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.
A Constructive Theory of Point-Set Nearness
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3667/1/159Bridges.pdf
File
MD5
7f8723fcb52e4f2ba4bf8c0d81add774
175992
application/pdf
159Bridges.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3667/2/159Bridges.pdf.txt
File
MD5
de17dc14499abc1185b7ff4d812aafd6
34294
text/plain
159Bridges.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3749
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Juarna, A
2009-04-16T23:10:16Z
2004-07
CDMTCS Research Reports CDMTCS-242 (2004)
1178-3540
http://hdl.handle.net/2292/3749
[no abstract available]
Fast Generation of Fibonacci Permutations
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3749/1/242vincent.pdf
File
MD5
ec8875ea5b2d13430561a8fd18a2b6ab
216807
application/pdf
242vincent.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3749/2/242vincent.pdf.txt
File
MD5
4027874738f9453ae23fc1e95e06e990
17711
text/plain
242vincent.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3593
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Breaking the Turing Barrier
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3593/1/084turing.pdf
File
MD5
6958a47bc557c371a9b3a5c7233c7941
144362
application/pdf
084turing.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3593/2/084turing.pdf.txt
File
MD5
a97ec941ae54bf85244cdd72a59f3b6d
8767
text/plain
084turing.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3600
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Dinneen, M.J
2009-04-16T23:10:20Z
1998-10
CDMTCS Research Reports CDMTCS-091 (1998)
1178-3540
http://hdl.handle.net/2292/3600
[no abstract available]
Abstracts of the 2nd Japan - New Zealand Workshop on Logic in Computer Science
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3600/1/091mjd.pdf
File
MD5
c43272a04b46ea6299a9856342e90e63
147780
application/pdf
091mjd.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3600/2/091mjd.pdf.txt
File
MD5
57532781342f3ac0ae7fc677687b8103
5824
text/plain
091mjd.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3791
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Most Short Programs Halt Quickly or Never Halt
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3791/1/284cris.pdf
File
MD5
e0753101497691211b10c2f3de5a49d8
600722
application/pdf
284cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3791/2/284cris.pdf.txt
File
MD5
f676fda4057eff7aba1ced64e1396a5b
35521
text/plain
284cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3772
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Stay, M
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.
Very Simple Chaitin Machines for Concrete AIT
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3772/1/265stay.pdf
File
MD5
dc09991619ab76108043fc5f896c879a
447308
application/pdf
265stay.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3772/2/265stay.pdf.txt
File
MD5
50d6dfb816f8eef0b9568ae28736ada9
38252
text/plain
265stay.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3644
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Downey, R.G
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.
Presentations of Computably Enumerable Reals
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3644/1/135rod.pdf
File
MD5
19400bc1005ba1a460c9631df7d21167
288575
application/pdf
135rod.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3644/2/135rod.pdf.txt
File
MD5
cdd13e14cc2d93c1fe2d42fc6670f332
77623
text/plain
135rod.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3521
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Antoniou, I
2009-04-16T23:10:25Z
1996-04
CDMTCS Research Reports CDMTCS-012 (1996)
1178-3540
http://hdl.handle.net/2292/3521
[no abstract available]
Quantum Electronic Devices Based on Metal-Dielectric Transition in Low-Dimensional Quantum Structures
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3521/1/012borisp.pdf
File
MD5
1934aeb6b412f9c5715eb2925227c735
543323
application/pdf
012borisp.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3521/2/012borisp.pdf.txt
File
MD5
170604626ec330632f42377f8c6f172d
35137
text/plain
012borisp.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3645
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Svozil, K
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.
Quantum Interfaces
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3645/1/136karl.pdf
File
MD5
da6571fb28b54eefe350a6abb7e8c493
393061
application/pdf
136karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3645/2/136karl.pdf.txt
File
MD5
8cfdb05f35a992c51890442e1cb0a32e
36659
text/plain
136karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3522
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C
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.
Kraft-Chaitin Inequality Revisited
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3522/1/013cris2.pdf
File
MD5
61f0434b9401d821b9abc92dc02e6f25
490121
application/pdf
013cris2.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3522/2/013cris2.pdf.txt
File
MD5
431114d91c22e341b627b9a360297145
9660
text/plain
013cris2.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3795
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Lladser, M.E
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.
The Diameter of Random Cayley Digraphs of Given Degree
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3795/1/288wilson.pdf
File
MD5
59398fda4366ef7352d5cb1d4020100b
227161
application/pdf
288wilson.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3795/2/288wilson.pdf.txt
File
MD5
96388ef0427d81492b46b1a2040459ec
37938
text/plain
288wilson.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3591
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
2009-04-16T23:10:31Z
1998-05
CDMTCS Research Reports CDMTCS-082 (1998)
1178-3540
http://hdl.handle.net/2292/3591
[no abstract available]
News from New Zealand / Group-Theoretic Methods for Designing Networks
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3591/1/082nznews.pdf
File
MD5
803c606b99f72eb5152a3d4830c5bb1f
267895
application/pdf
082nznews.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3591/2/082nznews.pdf.txt
File
MD5
d46337c6dd228dd90fdd362e12a56995
14982
text/plain
082nznews.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3789
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Chaitin, G.J
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.
Speculations on Biology, Information and Complexity
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3789/1/282greg.pdf
File
MD5
bfcd59a0f1139c522444cdf5fcd60cae
139034
application/pdf
282greg.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3789/2/282greg.pdf.txt
File
MD5
a8d7bca66ae009e2b1fdfe67c9fe2aa5
17868
text/plain
282greg.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3773
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Eimann, R
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.
Network Event Detection with T-Entropy
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3773/1/266eimann.pdf
File
MD5
9c0cd4b31d35e23f94876c342ac534fa
439600
application/pdf
266eimann.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3773/2/266eimann.pdf.txt
File
MD5
46249bfb0879d754d889222c53a8c414
25562
text/plain
266eimann.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3642
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Kearse, M.D
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.
Computational Methods and New Results for Chessboard Problems
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3642/1/133chess.pdf
File
MD5
eb6387b5930203576dc0471d924e8176
255369
application/pdf
133chess.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3642/2/133chess.pdf.txt
File
MD5
683ce27033e5f72665bbc163363b8332
60741
text/plain
133chess.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3607
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Paun, G
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.
Computing with Membranes: A Variant
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3607/1/098deltatau.pdf
File
MD5
a360a154e8d5ae7164ca6a276349fa91
219102
application/pdf
098deltatau.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3607/2/098deltatau.pdf.txt
File
MD5
92de86345263e4b1385631b31a1b7db9
33912
text/plain
098deltatau.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3592
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Computational Complementarity for Mealy Automata
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3592/1/083cec.pdf
File
MD5
7cb8524813037cd12c09d5afd2c5973a
360555
application/pdf
083cec.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3592/2/083cec.pdf.txt
File
MD5
3be89e04c64e74d770683ac1c39bc3f1
27157
text/plain
083cec.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3575
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Cazanescu, V.E
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.
Feedback for Relations
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3575/1/066virgil.pdf
File
MD5
27014b4ed8dd3096cc177be656f2fd16
514602
application/pdf
066virgil.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3575/2/066virgil.pdf.txt
File
MD5
9705e8821460bc087538a26b46411d2c
11527
text/plain
066virgil.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3788
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Chaitin, G.J
2009-04-16T23:10:42Z
2006-07
CDMTCS Research Reports CDMTCS-281 (2006)
1178-3540
http://hdl.handle.net/2292/3788
[no abstract available]
Is Incompleteness A Serious Problem
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3788/1/281greg.pdf
File
MD5
f81600b8f3543f7445e6807653319d63
104047
application/pdf
281greg.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3788/2/281greg.pdf.txt
File
MD5
f75392a03a4eeedf2e368a122e9fceaf
7581
text/plain
281greg.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3519
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Dediu, L
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.
Higman's Embedding Theorem. An Elementary Proof
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3519/1/010luminita.pdf
File
MD5
ff28f069ea5691a09430f027b06a917c
765510
application/pdf
010luminita.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3519/2/010luminita.pdf.txt
File
MD5
1b6504553af26e18eecf5151dcf66e61
74752
text/plain
010luminita.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3744
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Juergensen, H
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.
Finite Automata Encoding Geometric Figures
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3744/1/237ludwig.pdf
File
MD5
a9249943db07da26e49697d506e5918d
250800
application/pdf
237ludwig.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3744/2/237ludwig.pdf.txt
File
MD5
e23c28020471d2931057ee19831eafb0
39540
text/plain
237ludwig.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3848
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Müller, C
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.
Context-Aware Adaptation. A Case Study on Mathematical Notations
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3848/1/341christine.pdf
File
MD5
c6b12eb4db922deca29ab32bc99d6d8e
612343
application/pdf
341christine.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3848/2/341christine.pdf.txt
File
MD5
33074f2cc22731ee74bfa494d294de1d
91964
text/plain
341christine.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3775
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Greenberger, D.M
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.
Quantum Theory Looks at Time Travel
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3775/1/268karl.pdf
File
MD5
2bd72e7ae6a431d92349384bb7308e31
132264
application/pdf
268karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3775/2/268karl.pdf.txt
File
MD5
4d3b27c49b7dc2d20f7f8c39e6f1f77a
19105
text/plain
268karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3660
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Supplemental Abstracts for DMTCS01
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3660/1/152DMTCS01.pdf
File
MD5
43960ae266f44f3507fa08a7bd8bb83d
242160
application/pdf
152DMTCS01.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3660/2/152DMTCS01.pdf.txt
File
MD5
744dcfa8c645e1e9d74d625a22af9060
154268
text/plain
152DMTCS01.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3663
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Donath, N
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.
Finding a State in a Haystack
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3663/1/155karl.pdf
File
MD5
3a4f471acb3fdf7991cd6f09a31cf1fe
197634
application/pdf
155karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3663/2/155karl.pdf.txt
File
MD5
f72f5f666308b9a775eb9ccea9858280
115367
text/plain
155karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3719
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Terwijn, S.A
2009-04-16T23:10:52Z
2003-03
CDMTCS Research Reports CDMTCS-212 (2003)
1178-3540
http://hdl.handle.net/2292/3719
[no abstract available]
Complexity and Randomness
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3719/1/212bas.pdf
File
MD5
fe1dad5266463e14fa2c3060df03ebd9
447284
application/pdf
212bas.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3719/2/212bas.pdf.txt
File
MD5
65f7289fd7e4f527eda676a2a4805ab7
84665
text/plain
212bas.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3626
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
A Glimpse into Natural Computing
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3626/1/117cris.pdf
File
MD5
6db071c5a51f1e7976bc51fd07878d60
241880
application/pdf
117cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3626/2/117cris.pdf.txt
File
MD5
fd35a89bf7af30cb376b44b39f52c250
56517
text/plain
117cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3776
2012-02-02T23:23:12Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Svozil, K
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.
Characterization of Quantum Computable Decision Problems by State Discrimination
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3776/1/269karl.pdf
File
MD5
2559303cf827d8457625674872464270
142097
application/pdf
269karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3776/2/269karl.pdf.txt
File
MD5
f1869486874510f12af98e98b47c96db
32356
text/plain
269karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3641
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
The Poincare-Hardy Inequality on the Complement of a Cantor Set
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3641/1/132cris.pdf
File
MD5
e4b932bafb165c1f496acc9d9a38d1aa
692509
application/pdf
132cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3641/2/132cris.pdf.txt
File
MD5
07abdc1ddff814b593f5a85907bc2c74
34435
text/plain
132cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3868
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Svozil, K
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.
Three Criteria for Quantum Random Number Generators Based on Beam Splitters
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3868/1/362karl.pdf
File
MD5
a204cf9de5131b548bb1866e9dc3180f
157516
application/pdf
362karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3868/2/362karl.pdf.txt
File
MD5
1b3ff086fe14fc270af62d4bd0d50bd3
19716
text/plain
362karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3819
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
On Universal Computably Enumerable Prefix Codes
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3819/1/312cris.pdf
File
MD5
2d3284d05ed2117f12df4981a23a6eac
263868
application/pdf
312cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3819/2/312cris.pdf.txt
File
MD5
fd011d9d3b18d6b502b3a37c5ed5e12c
28217
text/plain
312cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3746
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
2009-04-16T23:11:01Z
2004-04
CDMTCS Research Reports CDMTCS-239 (2004)
1178-3540
http://hdl.handle.net/2292/3746
[no abstract available]
On Partial Randomness
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3746/1/239cris.pdf
File
MD5
77ef46176e024cd61e8911e9d589009d
190034
application/pdf
239cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3746/2/239cris.pdf.txt
File
MD5
a89fbf749e9d746ba11bf8e0962c1923
26814
text/plain
239cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3606
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Kraegeloh, A.M
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.
Unstable Dynamics on a Markov Background and Stability in Average
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3606/1/097alexander.pdf
File
MD5
f4cec04c42198c8ec56f54b38cd2bb82
1065308
application/pdf
097alexander.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3606/2/097alexander.pdf.txt
File
MD5
79a4ca5f1827792c283f03cccba602a9
232627
text/plain
097alexander.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3595
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
A Note on Pseudorandom Generators
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3595/1/086randgen.pdf
File
MD5
9955c225a78dcf3e9f1c5a59f5b776d8
211023
application/pdf
086randgen.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3595/2/086randgen.pdf.txt
File
MD5
591942142e1490789445ae61e2257973
19771
text/plain
086randgen.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3745
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Filipp, S
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.
The min-max Principle Generalizes Tsirelson's Bound
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3745/1/238karl.pdf
File
MD5
fc10b1a9f758175a3d15b1dbdc22015f
90834
application/pdf
238karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3745/2/238karl.pdf.txt
File
MD5
a5d140e2754fe39c20891eea8f1b739b
17655
text/plain
238karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3818
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Drape, S
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.
Design and Evaluation of Slicing Obfuscation
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3818/1/311stephen.pdf
File
MD5
ce5bfcc2319e1697b4c153002b8c5ce1
440438
application/pdf
311stephen.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3818/2/311stephen.pdf.txt
File
MD5
71851dd982427289fa9748aefa1e8bba
101710
text/plain
311stephen.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3688
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Passages of Proof
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3688/1/180proofs.pdf
File
MD5
902ba494ad2ee8dc162aac5e38384861
448177
application/pdf
180proofs.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3688/2/180proofs.pdf.txt
File
MD5
2e849bbf784e2aa65189376de2a3724a
60634
text/plain
180proofs.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3720
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Randomness Relative to Cantor Expansions
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3720/1/213cris.pdf
File
MD5
1f66ad2a508ea08a4f5e6bb8cbef53fe
210324
application/pdf
213cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3720/2/213cris.pdf.txt
File
MD5
9082dabd0e5e88d6aae14fc0a33368ae
24564
text/plain
213cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3846
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Simplicity via Provability for Universal Prefix-free Turing Machines
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3846/1/339cris.pdf
File
MD5
2a92f614eb3cb6dfd13e296b81c4e739
341042
application/pdf
339cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3846/2/339cris.pdf.txt
File
MD5
0607710be1263c9546266705eb3c5ade
17476
text/plain
339cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3813
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
2009-04-16T23:11:12Z
2007-05
CDMTCS Research Reports CDMTCS-306 (2007)
1178-3540
http://hdl.handle.net/2292/3813
[no abstract available]
Quantum Informatics and the Relations Between Informatics, Physics and Mathematics: A Dialogue
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3813/1/306cris.pdf
File
MD5
c90564ee78b39e56601222ab7126c2c6
372078
application/pdf
306cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3813/2/306cris.pdf.txt
File
MD5
0ad8d4942d0ff59beea3be6461954b58
69025
text/plain
306cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3545
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Embedding Quantum Universes into Classical Ones
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3545/1/036cris.pdf
File
MD5
ff70d0433bab75a1f5c5be3f6ed28354
494485
application/pdf
036cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3545/2/036cris.pdf.txt
File
MD5
beb71f7d8c5bc37f5e46e6cf080789cc
57351
text/plain
036cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3794
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Pritchard, G
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.
Probability Calculations Under the IAC Hypothesis
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3794/1/287wilson.pdf
File
MD5
71bc8f5a4f9b2e1a21faa2f84b549193
167923
application/pdf
287wilson.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3794/2/287wilson.pdf.txt
File
MD5
942f924c66db38e85f547dfaec55b05a
32478
text/plain
287wilson.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3814
2020-03-10T02:14:36Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Raichev, A
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].
Asymptotics of Diagonal Coefficients of Multivariate Generating Functions
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3814/1/307mcw.pdf
File
MD5
a8cde19d80b86fff7323db9045154ac2
212739
application/pdf
307mcw.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3814/2/307mcw.pdf.txt
File
MD5
bdfcb5210b0cf0eb6371889e18080697
17750
text/plain
307mcw.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3590
2012-02-02T23:23:18Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Arslanov, A
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.
On Hypersimple Sets and Chaitin Complexity
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3590/1/081asat.pdf
File
MD5
ccfc18bb939eca294c7006aea3e46617
338106
application/pdf
081asat.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3590/2/081asat.pdf.txt
File
MD5
010fa993d4d0e5a41e152ff69e63640d
23179
text/plain
081asat.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3666
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Grozea, C
2009-04-16T23:11:20Z
2001-07
CDMTCS Research Reports CDMTCS-158 (2001)
1178-3540
http://hdl.handle.net/2292/3666
[no abstract available]
Relations Between the Low Subrecursion Classes
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3666/1/158grozea.pdf
File
MD5
229e7b3d06cbd6a21b4d74866caeff51
3007070
application/pdf
158grozea.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3666/2/158grozea.pdf.txt
File
MD5
36c6f0b2061da514c400c0bc2749b5cf
12
text/plain
158grozea.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3547
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Richman, F
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
A Constructive Proof of Gleason's Theorem
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3547/1/038douglas.pdf
File
MD5
b1b180450d01aef2acaecc1f9d420075
297780
application/pdf
038douglas.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3547/2/038douglas.pdf.txt
File
MD5
9e2deaba65983ab15eabe0ef8dca05a0
50757
text/plain
038douglas.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3669
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
The Bridge Crossing Problem: Draft Form
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3669/1/161CE.pdf
File
MD5
fdc515b484fc2276d954e57047276048
518623
application/pdf
161CE.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3669/2/161CE.pdf.txt
File
MD5
20953aa70f8ea5ba1ae37c5a8ff7ff6c
18070
text/plain
161CE.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3599
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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 α.
Degree-Theoretic Aspects of Computably Enumerable Reals
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3599/1/090cris.pdf
File
MD5
67a00d1f8359da64298100fcdc5e7f08
333168
application/pdf
090cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3599/2/090cris.pdf.txt
File
MD5
04ed766a573e23f2d723feff21894990
50449
text/plain
090cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3750
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Stay, M
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.
Inexpensive Linear-Optical Implementations of Deutsch's Algorithm
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3750/1/243mike.pdf
File
MD5
1180b71ec00b75a458b6a452037b7f45
353070
application/pdf
243mike.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3750/2/243mike.pdf.txt
File
MD5
b749750901baeee742271e40f4925d62
11433
text/plain
243mike.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3714
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Khoussainov, B
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
Games on Graphs: Automata, Structure, and Complexity
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3714/1/207bmk.pdf
File
MD5
78287d1fcc3d12ed079ba2efafb2eb84
228137
application/pdf
207bmk.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3714/2/207bmk.pdf.txt
File
MD5
75a93b8bdc45f08c02d1de44a0a2aa04
39289
text/plain
207bmk.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3548
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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
A Genius' Story: Two Books on Godel
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3548/1/039cris.pdf
File
MD5
94b89e43a5444afcc4e5e438a91e2d19
254901
application/pdf
039cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3548/2/039cris.pdf.txt
File
MD5
39cc90433177ff46566b422da9832ae0
26284
text/plain
039cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3623
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Chaitin $\Omega$ Numbers, Solovay Machines, and Incompleteness
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3623/1/114cris.pdf
File
MD5
28fe0a56fb10039dc58b821668ffde03
158645
application/pdf
114cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3623/2/114cris.pdf.txt
File
MD5
77209067a907051ced0515596b7fe530
19322
text/plain
114cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3767
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Ishihara, H
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.
Quasi-Apartness and Neighbourhood Spaces
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3767/1/260hajime.pdf
File
MD5
c2a6a1874379084ec8980036eadee2bb
261363
application/pdf
260hajime.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3767/2/260hajime.pdf.txt
File
MD5
de712be7cc1a5e297800126ac9de46d9
141954
text/plain
260hajime.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3753
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Computing with Cells and Atoms: After Five Years
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3753/1/246cris.pdf
File
MD5
89acc4ee5383d61b0ac4b0bfcde976c6
218231
application/pdf
246cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3753/2/246cris.pdf.txt
File
MD5
0ea2f0980fe39502e25a894a4308619c
63368
text/plain
246cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3692
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Svozil, K
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.
n-ary Quantum Information Defined by State Partitions
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3692/1/184karl.pdf
File
MD5
ce95daa50e256ee3615697e818272064
69224
application/pdf
184karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3692/2/184karl.pdf.txt
File
MD5
d514ffff71a3d9aa8e5fa643a09d2f9c
23268
text/plain
184karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3748
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Is Complexity a Source of Incompleteness?
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3748/1/241cris.pdf
File
MD5
17476e8ac82740c99c075656aa634b89
672303
application/pdf
241cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3748/2/241cris.pdf.txt
File
MD5
a74cab82863419cb90c2dd133c64283a
41278
text/plain
241cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3597
2020-03-09T01:54:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Staiger, L
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.
The Hausdorff Measure of Regular Omega-Languages is Computable
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3597/1/088ludwig.pdf
File
MD5
5f42f66a0eda30e954d703ecd669765b
238416
application/pdf
088ludwig.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3597/2/088ludwig.pdf.txt
File
MD5
479e074df98dcac2bcf8b959d69aa90f
9946
text/plain
088ludwig.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3594
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Denny, P.C
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.
Search and Enumeration Techniques for Incidence Structures
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3594/1/085denny.pdf
File
MD5
0d1c4580ac12a8b1280e27ea726fb3c3
1282878
application/pdf
085denny.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3594/2/085denny.pdf.txt
File
MD5
f093ea633cf9bf14eaf30334fdeea4c5
688105
text/plain
085denny.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3694
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Arulanandham, J.J
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.
Implementing Bead--Sort with P systems
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3694/1/186joshua.pdf
File
MD5
b345184f4c02defd65e8c59207b1b08e
729335
application/pdf
186joshua.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3694/2/186joshua.pdf.txt
File
MD5
10c4d1c46dda5d4e57f16d7c18061264
68867
text/plain
186joshua.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3572
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Disjunctive Sequences: An Overview
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3572/1/063cris.pdf
File
MD5
acf04399d31b54a5bfad958c68088969
900594
application/pdf
063cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3572/2/063cris.pdf.txt
File
MD5
db7d5069df04f9946b62a2ae50dc15cf
87678
text/plain
063cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3689
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Khoussainov, B
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.
Computable Isomorphism of Boolean Algebras with Operators
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3689/1/181bmk.pdf
File
MD5
bf3e4f823c71bcc0ec3adc4d07bdcca6
133965
application/pdf
181bmk.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3689/2/181bmk.pdf.txt
File
MD5
49ebdcbccdf93fe94190bd838e227805
21713
text/plain
181bmk.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3526
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Khoussainov, B
2009-04-16T23:11:45Z
1996-08
CDMTCS Research Reports CDMTCS-017 (1996)
1178-3540
http://hdl.handle.net/2292/3526
[no abstract available]
Randomness, Computability, and Algebraic Specifications
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3526/1/017bmk.pdf
File
MD5
bd2e8e5869308b89ba0312cd26ced520
481867
application/pdf
017bmk.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3526/2/017bmk.pdf.txt
File
MD5
4684fa716be04de9bf8097b59a42b344
34612
text/plain
017bmk.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3725
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Generalisations of Disjunctive Sequences
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3725/1/218cris.pdf
File
MD5
4670853086f1716d424d00a297efb998
227477
application/pdf
218cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3725/2/218cris.pdf.txt
File
MD5
dfdb7228771287376167b53c8725f6d0
27372
text/plain
218cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3639
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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?
Reflections on Quantum Computing
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3639/1/130cris.pdf
File
MD5
bce2c383fbacefb79424b090663c5c95
467566
application/pdf
130cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3639/2/130cris.pdf.txt
File
MD5
c80e85cabfa69d6d37706a052c90fdc8
14415
text/plain
130cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3687
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Svozil, K
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.
Logical Equivalence Between Generalized Urn Models and Finite Automata
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3687/1/179karl.pdf
File
MD5
84d9d1d8d52c5f0f103c18122e5f2dbd
56747
application/pdf
179karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3687/2/179karl.pdf.txt
File
MD5
267073ae45661d40983ad6bbe182be98
20327
text/plain
179karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3565
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Bridges, D.S
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.
Paradise Lost, or Paradise Regained?
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3565/1/056douglas.pdf
File
MD5
bd2e2be279c0ff3196b630d2bafdb791
466346
application/pdf
056douglas.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3565/2/056douglas.pdf.txt
File
MD5
ecd93e8094e24d0c7b6911757c017d1d
85365
text/plain
056douglas.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3540
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Khoussainov, B
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.
Computable Isomorphisms, Degree Spectra of Relations, and Scott Families
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3540/1/031bmk.pdf
File
MD5
39dbe31d12dc61e459153afb418d2509
454685
application/pdf
031bmk.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3540/2/031bmk.pdf.txt
File
MD5
a58e4045bd74310b5ccac773476b401a
117786
text/plain
031bmk.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3668
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Meyerstein, F.W
2009-04-16T23:11:54Z
2001-09
CDMTCS Research Reports CDMTCS-160 (2001)
1178-3540
http://hdl.handle.net/2292/3668
[no abstract available]
LifeTime: A Unified Study of Life (A Preliminary Version)
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3668/1/160MM.pdf
File
MD5
b1b50cb693d48c937e2bcdadb38a9a0b
1576882
application/pdf
160MM.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3668/2/160MM.pdf.txt
File
MD5
be08aa6dd99590a1f1b0755cbfa5003c
563268
text/plain
160MM.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3752
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Harmer, M.
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.
Fitting Parameters for a Solvable Model of a Quantum Network (CDMTCS)
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3752/1/245mark.pdf
File
MD5
4c1efed3e8b42f15cee5c95cb182e23f
191658
application/pdf
245mark.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3752/2/245mark.pdf.txt
File
MD5
fcedfbd71e484c20d424885ec3b28960
16919
text/plain
245mark.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3611
2012-02-02T23:23:16Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Paun, G
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.
P Systems with Active Membranes: Attacking NP Complete Problems
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3611/1/102paun.pdf
File
MD5
401eb719cde471569eedddcdc6e4d8b5
277948
application/pdf
102paun.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3611/2/102paun.pdf.txt
File
MD5
5c3e185de3bf229d00d96b00a6be6ce6
42225
text/plain
102paun.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3715
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Khoussainov, B
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.
Automatic linear orders and trees (Revised)
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3715/1/208rubin.pdf
File
MD5
c6ea71abcdf06e639c6fcc038e715312
452665
application/pdf
208rubin.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3715/2/208rubin.pdf.txt
File
MD5
e20eb9da8290cc9325a347b8c6285958
312275
text/plain
208rubin.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3681
2012-02-02T23:23:17Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Downey, R.G
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.
Some Computability-Theoretical Aspects of Reals and Randomness
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3681/1/173rod.pdf
File
MD5
1ae1d95ab16e437cd959acdcc8a71c0c
523091
application/pdf
173rod.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3681/2/173rod.pdf.txt
File
MD5
db954cfd53173493191a1a7b8e1db8ab
208854
text/plain
173rod.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3726
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Dialogues on Quantum Computing
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3726/1/219cris.pdf
File
MD5
71981ad6b3677bdc703ccc2a309ab5fd
137514
application/pdf
219cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3726/2/219cris.pdf.txt
File
MD5
d5a67f62e7d88de3cfc990b167793d13
30327
text/plain
219cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3578
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Bridges, D.S
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.
Adjoints, Absolute Values and Polar Decompostions
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3578/1/069douglas.pdf
File
MD5
cb17b7da499fe7f29d7e91390825b252
579739
application/pdf
069douglas.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3578/2/069douglas.pdf.txt
File
MD5
07e95987fb48bc0b85d75c97eca6d50e
22809
text/plain
069douglas.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3612
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Assanovich, B
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.
Variable-Length Codes for Sources with Equiprobable Symbols
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3612/1/103boris.pdf
File
MD5
31efaf44b607be5ef67273482e127240
209537
application/pdf
103boris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3612/2/103boris.pdf.txt
File
MD5
7a3ba63f197fd3cc49b46f028958f319
14710
text/plain
103boris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3621
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Solving Problems with Finite Test Sets
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3621/1/112cris.pdf
File
MD5
87ff0864536ffd04d7d8a61f78483dde
192729
application/pdf
112cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3621/2/112cris.pdf.txt
File
MD5
5299e1ccbfdacdb936990fb1e1d90f42
26811
text/plain
112cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3821
2012-02-02T23:23:13Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Goles, E
2009-04-16T23:12:07Z
2007-11
CDMTCS Research Reports CDMTCS-314 (2007)
1178-3540
http://hdl.handle.net/2292/3821
The Underlying Optimal Protocol of Rule 218 Cellular Automaton
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3821/1/314eric.pdf
File
MD5
87c047da450434fd72a4959ca8373e17
277636
application/pdf
314eric.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3821/2/314eric.pdf.txt
File
MD5
94dab78646710e9bee8b2472554cfe50
17559
text/plain
314eric.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3740
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Svozil, K
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.
Quantum Information via State Partitions and the Context Transition Principle
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3740/1/233karl.pdf
File
MD5
f72844c3baba126470a85ffbcdcf4da5
80078
application/pdf
233karl.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3740/2/233karl.pdf.txt
File
MD5
26c25595d057bf88e2efb69e7bf8abfc
25859
text/plain
233karl.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3528
2012-02-02T23:23:14Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Dinneen, Michael
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.
Forbidden Minors to Graphs with Small Feedback Sets
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3528/1/019mjd.pdf
File
MD5
2da18c5bd6fd8a79aa1c0f811c90ddf8
686268
application/pdf
019mjd.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3528/2/019mjd.pdf.txt
File
MD5
ae35ca3ff3d007346a9833244bc1b37e
80520
text/plain
019mjd.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3835
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Calude, C.S
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.
Every Computably Enumerable Random Real Is Provably Computably Enumerable Random
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3835/1/328cris.pdf
File
MD5
79b5a2799a3c187dc79777dbbc4f04ec
394959
application/pdf
328cris.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3835/2/328cris.pdf.txt
File
MD5
6cf2705161a9af9e381c9b39adcb12e6
52335
text/plain
328cris.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3836
2012-02-02T23:23:19Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Dinneen, Michael
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.
A New Linear-Time Dominating Number Algorithm for Graphs of Bounded Pathwidth
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3836/1/329mjd.pdf
File
MD5
913bac25fdb7e910be26adfa6d3e3c74
406721
application/pdf
329mjd.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3836/2/329mjd.pdf.txt
File
MD5
5a176fd76a203645bb3587596f704e66
33831
text/plain
329mjd.pdf.txt
oai:researchspace.auckland.ac.nz:2292/3805
2012-02-02T23:23:15Z
com_2292_122
col_2292_3508
ResearchSpace 3.2 at The University of Auckland
author
Staiger, L
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.
Prefix-free Lukasiewicz Languages
Technical Report
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3805/1/298ludwig.pdf
File
MD5
bcabf0b15166f12d2177f181aa7a31f8
141952
application/pdf
298ludwig.pdf
URL
https://researchspace.auckland.ac.nz/bitstream/2292/3805/2/298ludwig.pdf.txt
File
MD5
38011bebc40102009de99aa481428a49
16504
text/plain
298ludwig.pdf.txt
MToxMDB8Mjpjb2xfMjI5Ml8zNTA4fDM6fDQ6fDU6bWV0cw==