2,282 results for Report

• The Tiling of the Hyperbolic 4D Space by the 120-Cell Is Combinatoric

Margenstern, M (2003-02)

Report
The University of Auckland Library

The splitting method, which was defined by the author in [9,10] is at the basis of the notion of combinatoric tilings. As a consequence of this notion, there is a recurrence sequence which allows us to compute the number of tiles which are at a fixed distance from a given tile. A polynomial is attached to the sequence as well as a language which can be used for implementing cellular automata on the tiling. We give here the polynomial and, as a first consequence, the language of the splitting is not regular, as it is the case in the tiling of hyperbolic 3D space by regular dodecahedra which is also combinatoric.

View record details
• Independence in Database Relations

Kontinen, J; Link, S; Väänänen, J (2013)

Report
The University of Auckland Library

We investigate the implication problem for independence atoms X?Y of dis- joint attribute sets X and Y on database schemata. A relation satisfi es X?Y if for every X-value and every Y -value that occurs in the relation there is some tuple in the relation in which the X-value occurs together with the Y -value. We establish an axiomatization by a finite set of Horn rules, and derive an algorithm for deciding the implication problem in low-degree polynomial time in the input. We show how to construct Armstrong relations which satisfy an arbitrarily given set of independence atoms and violate every independence atom not implied by the given set. Our results establish independence atoms as an e fficient subclass of embedded multivalued data dependencies which are not axiomatizable by a finite set of Horn rules, and whose implication problem is undecidable.

View record details
• Computing with Membranes (P Systems): Twenty Six Research Topics

Paun, G (2000-02)

Report
The University of Auckland Library

The aim of these notes is to state a series of open problems and, mainly, research topics about P systems. They can be clustered in three classes: questions dealing with “classic” topics in automata and language theory, questions motivated by the possible usefulness of P systems as computing models (implementation and complexity issues), and questions related to the fields where the P systems are inspired from, biology and biochemistry. Precise open problems can be found practically in all papers published or distributed so far on the web; here we are mainly interested in research directions, in classes of problems.

View record details
• Comparing Two Local Searches in a (1+1) Restart Memetic Algorithm on the Clique Problem

Wei, K; Dinneen, MJ (2013)

Report
The University of Auckland Library

In recent years, the advantage afforded by using multiple local searches in a Memetic Algorithm to solve one problem (a single fitness function), has been verified in many successful experiments. However, theoretical studies cannot explain why Memetic Algorithms with multiple local searches often outperform Memetic Algorithms with a single local search in these experiments. In this paper, we will formalize a (1+1) Restart Memetic Algorithm and two different local searches, and run them on a single fitness function to solve the Clique Problem. We then show that there are two families of graphs such that, for the first family of graphs, Memetic Algorithms with one local search drastically outperform Memetic Algorithms with the other local search, and vice versa for the second family of graphs. Furthermore, we propose a (1+1) Restart Memetic Algorithm with an Alternative Local Search, and show that the proposed algorithm is expected to solve the Clique Problem on both families of graphs efficiently. Lastly, we verify our theoretical results by experiments.

View record details
• Algorithmic Randomness, Quantum Physics, and Incompleteness

Calude, C.S (2004-08)

Report
The University of Auckland Library

Is randomness in quantum mechanics “algorithmically random”? Is there any relation between Heisenberg’s uncertainty relation and G¨odel’s incompleteness? Can quantum randomness be used to trespass the Turing’s barrier? Can complexity shed more light on incompleteness? In this paper we use variants of “algorithmic complexity” to discuss the above questions.

View record details
• Finite State Incompressible Infinite Sequences

Calude, CS; Staiger, L; Stephan, F (2013)

Report
The University of Auckland Library

In this paper we define and study finite state complexity dips in infinite sequences and finite state incompressible infinite sequences. We show that the finite state complexity does not only depend on the codes for finite transducers, but also on how the codes are mapped to transducers. As a consequence we relate the finite state complexity to the plain (Kolmogorov) complexity, to the process complexity and to prefix complexity. Working with prefix-free sets of codes we characterise Martin-Lof random sequences in terms of finite state complexity: the weak power of finite transducers is compensated by the high complexity of enumeration of finite transducers. We also prove that every finite state incompressible sequence is normal, but the converse implication is not true. These results also show that our definition of finite state incompressibility is stronger than all other known forms of finite automata based incompressibility in particular the notion related to finite automaton based betting systems introduced in [25]. The paper concludes with a discussion of open questions.

View record details
• Unconventional Models of Computation'98: Posters

Hertling, P (1998-01)

Report
The University of Auckland Library

The First International Conference on Unconventional Models of Computation, UMC'98, organized by the Centre for Discrete Mathematics and Theoretical Computer Science, in cooperation with the Santa Fe Institute, was held at the University of Auckland from January 5{9, 1998. The proceedings of UMC'98 have appeared in the DMTCS Series of Springer-Verlag, Singapore. This CDMTCS Research Report contains the abstracts or extended abstracts of the poster session contributions to UMC'98. They cover engineering, physical, mathematical, and philosophical aspects of a broad range of unconventional models of computation: from evolutionary computation, quantum computation, DNA{computing, molecular computing, new developments in probabilistic computation, and cellular automata to the question of electronic simulation of the human mind. Thanks to all participants for their interesting contributions.

View record details
• Multiset Processing by means of Systems of Sequential Transducers

Paun, G; Thierrin, G (1999-04)

Report
The University of Auckland Library

We introduce a computing mechanism of a biochemical inspiration (similar to a P system in the area of computing by membranes) which consists of a multiset of symbol-objects and a set of finite state sequential transducers. The transducers process symbols in the current multiset in the usual manner. A computation starts in an initial configuration and ends in halting configuration. The power of these mechanisms is investigated (the main result says that systems with two components generate all gsm images of all permutations of recursively enumerable languages), as well as the closure properties of the obtained family (which is shown to be a full AFL).

View record details
• Bio-Steps Beyond Turing

Calude, C.S; Paun, G (2003-11)

Report
The University of Auckland Library

Are there ‘biologically computing agents’ capable to compute Turing uncomputable functions? It is perhaps tempting to dismiss this question with a negative answer. Quite the opposite, for the first time in the literature on molecular computing we contend that the answer is not theoretically negative. Our results will be formulated in the language of membrane computing (P systems). Some mathematical results presented here are interesting in themselves. In contrast with most speed-up methods which are based on non-determinism, our results rest upon some universality results proved for deterministic P systems. These results will be used for building “accelerated P systems”. In contrast with the case of Turing machines, acceleration is a part of the hardware (not a quality of the environment) and it is realised either by decreasing the size of “reactors” or by speeding-up the communication channels. Consequently, two acceleration postulates of biological inspiration are introduced; each of them poses specific questions to biology. Finally, in a more speculative part of the paper, we will deal with Turing non-computability activity of the brain and possible forms of (extraterrestrial) intelligence.

View record details
• Obstructions for the Graphs of Vertex Cover Seven

Dinneen, Michael; Versteegen, Ralph (2012-12)

Report
The University of Auckland Library

In this paper we present an optimized procedure for computing the minor-order obstructions for graphs of vertex cover at most $k$. This extends the earlier method and results of Cattell and Dinneen in 1994, for $k \leq 5$. Here we extended the known set of forbidden graphs for $k \leq 7$. To help reduce the size of these sets, we also mention some proposals for finding minimal forbidden graphs for other stronger'' graph partial orders such as the $Y$-$\Delta$ and $H$-bowtie orders. We briefly mention our plans to incorporate these new features within our distributed computational framework (aka, VACS) for computing obstruction within the universe of bounded pathwidth and treewidth.

View record details
• Indeterminism and Randomness

Calude, CS (2015)

Report
The University of Auckland Library

Quantum randomness is postulated and generally reduced to the indeterminism of quantum measurements. The connection to randomness is often made via unpredictability: because the outcome is indeterministic there is no way to predict it, hence it is random. Here we argue that indeterminism and randomness are theoretical, means relative, concepts which don’t imply each other.

View record details
• Quasiperiods, Subword Complexity and the Smallest Pisot Number

Polley, R; Staiger, L (2015)

Report
The University of Auckland Library

A quasiperiod of a word or an infinite string is a word which covers every part of the string. A word or an infinite string is referred to as quasiperiodic if it has a quasiperiod. It is obvious that a quasiperiodic infinite string cannot have every word as a subword (factor). Therefore, the question arises how large the set of subwords of a quasiperiodic infinite string can be [Mar04]. Here we show that on the one hand the maximal subword complexity of quasiperiodic infinite strings and on the other hand the size of the sets of maximally complex quasiperiodic infinite strings both are intimately related to the smallest Pisot number tP (also known as plastic constant). We provide an exact estimate on the maximal subword complexity for quasiperiodic infinite words.

View record details
• Proceedings of the Workshop on Membrane Computing 2015 (WMC2015)

(2015)

Report
The University of Auckland Library

We present a new variant of how catalytic P systems can simulate register machines, thus reducing again the number of rules needed for simulating register machines. Moreover, we show that only 20 rules are needed to generate a non-semilinear set of natural numbers by a catalytic P system with two catalysts. Finally, we establish improved versions of universal catalytic P systems.

View record details
• A Non-Probabilistic Model of Relativised Predictability in Physics

Abbott, AA; Calude, CS; Svozil, K (2015)

Report
The University of Auckland Library

Little effort has been devoted to studying generalised notions or models of (un)predictability, yet is an important concept throughout physics and plays a central role in quantum information theory, where key results rely on the supposed inherent unpredictability of measurement outcomes. In this paper we continue the programme started in developing a general, non-probabilistic model of (un)predictability in physics. We present a more refined model that is capable of studying different degrees of “relativised” unpredictability. This model is based on the ability for an agent, acting via uniform, effective means, to predict correctly and reproducibly the outcome of an experiment using finite information extracted from the environment. We use this model to study further the degree of unpredictability certified by different quantum phenomena, showing that quantum complementarity guarantees a form of relativised unpredictability that is weaker than that guaranteed by Kochen-Specker-type value indefiniteness. We exemplify further the difference between certification by complementarity and value indefiniteness by showing that, unlike value indefiniteness, complementarity is compatible with the production of computable sequences of bits.

View record details
• How Large is the Set of Disjunctive Sequences?

Staiger, L (2002-01)

Report
The University of Auckland Library

We consider disjunctive sequences, that is, infinite sequences (ω-words) having all finite words as infixes. It is shown that the set of all disjunctive sequences can be described in an easy way using recursive languages and, besides being a set of measure one, is a residual set in Cantor space. Moreover, we consider the subword complexity of sequences: here disjunctive sequences are shown to be sequences of maximal complexity. Along with disjunctive sequences we consider the set of real numbers having disjunctive expansions with respect to some bases and to all bases. The latter are called absolutely disjunctive real numbers. We show that the set of absolutely disjunctive reals is also a residual set and has representations in terms of recursive languages similar to the ones in case of disjunctive sequences. To this end we derive some fundamental properties of the functions translating a base r-expansion of a real α Є [0,1] into α.

View record details
• Bibliography of Publications by John R. Womersley: Pioneer of Modern Computing and Applied Mathematician

Carpenter, BE; Doran, RW (2015)

Report
The University of Auckland Library

This bibliography was compiled in connection with a biographical article about John Ronald Womersley (1907-1958). He was an applied mathematician, then a manager of mathematicians and statisticians, in war and in peacetime. Then he was in at the beginning of electronic computers. Finally he made a difficult career transition in the mid 1950s from second-level management back to very successful applied mathematics research, before his early death.

View record details
• The Physical World as a Virtual Reality

Whitworth, B (2007-12)

Report
The University of Auckland Library

This paper explores the idea that the universe is a virtual reality created by information processing, and relates this strange idea to the findings of modern physics about the physical world. The virtual reality concept is familiar to us from online worlds, but our world as a virtual reality is usually a subject for science fiction rather than science. Yet logically the world could be an information simulation running on a three-dimensional space-time screen. Indeed, if the essence of the universe is information, matter, charge, energy and movement could be aspects of information, and the many conservation laws could be a single law of information conservation. If the universe were a virtual reality, its creation at the big bang would no longer be paradoxical, as every virtual system must be booted up. It is suggested that whether the world is an objective reality or a virtual reality is a matter for science to resolve. Modern information science can suggest how core physical properties like space, time, light, matter and movement could derive from information processing. Such an approach could reconcile relativity and quantum theories, with the former being how information processing creates space-time, and the latter how it creates energy and matter.

View record details
• Shift-Invariant Topologies for the Cantor Space X^omega

Hoffman, S; Schwarz, S; Staiger, L (2016)

Report
The University of Auckland Library

The space of one-sided infinite words plays a crucial rôle in several parts of Theoretical Computer Science. Usually, it is convenient to regard this space as a metric space, the CANTOR space. It turned out that for several purposes topologies other than the one of the CANTOR space are useful, e.g. for studying fragments of first-order logic over infinite words or for a topological characterisation of random infinite words. It is shown that these topologies refine the topology of the CANTOR space. Moreover, from common features of these topologies we extract properties which characterise a large class of topologies. It turns out that, for this general class of topologies, the corresponding closure and interior operators respect the shift operations and also, to some extent, the definability of sets of infinite words by finite automata.

View record details
• A Variant of the Kochen-Specker Theorem Localising Value Indefiniteness (Revision1)

Abbott, AA; Calude, CS; Svozil, K (2015)

Report
The University of Auckland Library

The Kochen-Specker theorem proves the inability to assign, simultaneously, noncontextual definite values to all (of a finite set of) quantum mechanical observables in a consistent manner. If one assumes that any definite values behave noncontextually, one can nonetheless only conclude that some observables (in this set) are value indefinite. In this paper we prove a variant of the Kochen-Specker theorem showing that, under the same assumption of noncontextuality, if a single one-dimensional projection observable is assigned the definite value 1, then no one-dimensional projection observable that is incompatible (i.e., non-commuting) with this one can be assigned consistently a definite value. Unlike standard proofs of the Kochen-Specker theorem, in order to localise and show the extent of value indefiniteness this result requires a constructive method of reduction between Kochen-Specker sets. If a system is prepared in a pure state |yi, then it is reasonable to assume that any value assignment (i.e., hidden variable model) for this system assigns the value 1 to the observable projecting onto the onedimensional linear subspace spanned by |yi, and the value 0 to those projecting onto linear subspaces orthogonal to it. Our result can be interpreted, under this assumption, as showing that the outcome of a measurement of any other incompatible one-dimensional projection observable cannot be determined in advance, thus formalising a notion of quantum randomness.

View record details