2,282 results for Report

The Tiling of the Hyperbolic 4D Space by the 120Cell Is Combinatoric
Margenstern, M (200302)
Report
The University of Auckland LibraryThe 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 LibraryWe 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 Xvalue and every Y value that occurs in the relation there is some tuple in the relation in which the Xvalue 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 lowdegree 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 (200002)
Report
The University of Auckland LibraryThe 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 LibraryIn 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 (200408)
Report
The University of Auckland LibraryIs 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 LibraryIn 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 prefixfree sets of codes we characterise MartinLof 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 (199801)
Report
The University of Auckland LibraryThe 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 SpringerVerlag, 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 (199904)
Report
The University of Auckland LibraryWe 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 symbolobjects 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 
BioSteps Beyond Turing
Calude, C.S; Paun, G (200311)
Report
The University of Auckland LibraryAre 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 speedup methods which are based on nondeterminism, 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 speedingup 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 noncomputability 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 (201212)
Report
The University of Auckland LibraryIn this paper we present an optimized procedure for computing the minororder 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 LibraryQuantum 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 LibraryA 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 LibraryWe 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 nonsemilinear 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 NonProbabilistic Model of Relativised Predictability in Physics
Abbott, AA; Calude, CS; Svozil, K (2015)
Report
The University of Auckland LibraryLittle 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, nonprobabilistic 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 KochenSpeckertype 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 (200201)
Report
The University of Auckland LibraryWe 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 rexpansion 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 LibraryThis bibliography was compiled in connection with a biographical article about John Ronald Womersley (19071958). 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 secondlevel management back to very successful applied mathematics research, before his early death.
View record details 
The Physical World as a Virtual Reality
Whitworth, B (200712)
Report
The University of Auckland LibraryThis 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 threedimensional spacetime 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 spacetime, and the latter how it creates energy and matter.
View record details 
ShiftInvariant Topologies for the Cantor Space X^omega
Hoffman, S; Schwarz, S; Staiger, L (2016)
Report
The University of Auckland LibraryThe space of onesided 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 firstorder 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 KochenSpecker Theorem Localising Value Indefiniteness (Revision1)
Abbott, AA; Calude, CS; Svozil, K (2015)
Report
The University of Auckland LibraryThe KochenSpecker 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 KochenSpecker theorem showing that, under the same assumption of noncontextuality, if a single onedimensional projection observable is assigned the definite value 1, then no onedimensional projection observable that is incompatible (i.e., noncommuting) with this one can be assigned consistently a definite value. Unlike standard proofs of the KochenSpecker theorem, in order to localise and show the extent of value indefiniteness this result requires a constructive method of reduction between KochenSpecker 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 onedimensional projection observable cannot be determined in advance, thus formalising a notion of quantum randomness.
View record details 
Probabilistic Cardinality Constraints
Roblot, TK; Link, S (2015)
Report
The University of Auckland LibraryProbabilistic databases address well the requirements of an increasing number of modern applications that produce large collections of uncertain data. We propose probabilistic cardinality constraints as a principled tool to control the occurrences of data patterns in probabilistic databases. Our constraints help balance the consistency and completeness targets for the quality of an organization's data, and can be used to predict with which probability a given number of query answers will be returned without actually querying the data. These target applications are unlocked by developing algorithms to reason efficiently about probabilistic cardinality constraints, and to help analysts acquire the marginal probability by which cardinality constraints should hold in a given application domain. For this purpose, we overcome technical challenges to compute Armstrong PCsketches as succinct data samples that perfectly visualize any given perceptions about these marginal probabilities.
View record details