Accepted papers

The accepted papers were published in the conference proceedings volume

by Springer, available online at the SpringerLink web site.

• Alastair A. Abbott and Cristian S. Calude. Von Neumann Normalisation and Symptoms of Randomness: An Application to Sequences of Quantum Random Bits
  Due to imperfections in measurement and hardware, the flow of bits generated by a quantum random number generator (QRNG) contains bias and correlation, two symptoms of non-randomness. There is no algorithmic method to eliminate correlation as this amounts to guaranteeing incomputability. However, bias can be mitigated: QRNGs use normalisation techniques such as von Neumann's method-the first and simplest technique for reducing bias-and other more efficient modifications. In this paper we study von Neumann un-biasing normalisation for an ideal QRNG operating 'to infinity', i.e. producing an infinite bit sequence. We show that, surprisingly, von Neumann un-biasing normalisation can both increase or decrease the (algorithmic) randomness of the generated sequences. The impact this has on the quality of incomputability of sequences of bits from QRNGs is discussed. A successful application of von Neumann normalisation-in fact, any un-biasing transformation-does exactly what it promises, un-biasing, one (among infinitely many) symptoms of randomness; it will not produce 'true' randomness, a mathematically vacuous concept.
• Selim Akl and Naya Nagy. Computations with Uncertain Time Constraints: Effects on Parallelism and Universality
  It is known that there exist computational problems that can be solved on a parallel computer, yet are impossible to be solved sequentially. Specifically, no general purpose sequential model of computation, such as the Turing Machine or the Random Access Machine, can simulate a large family of computations (for example, solutions to certain real-time problems), each of which is capable of being carried out readily by a particular parallel computer. We extend the scope of such problems to the class of problems with uncertain time constraints. The first type of time constraints refers to uncertain time requirements on the input data, that is, when and for how long are the input data available. A second type of time constraints refers to uncertain deadlines for tasks. Our main objective is to exhibit computational problems in which it is very difficult to find out (read "compute") what to do and when to do it. Furthermore, problems with uncertain time constraints, as described here, prove once more that it is impossible to define a "universal computer", that is, a computer able to compute all computable functions. Finally, one of the contributions of this paper is to promote the study of a topic, conspicuously absent to date from theoretical computer science, namely, the role of physical time and physical space in computation. The focus of our work is to analyze the effect of external natural phenomena on the various components of a computational process, namely, the input phase, the calculation phase (including the algorithm and the computing agents themselves), and the output phase.
• Olivier Bouré, Nazim Fatès and Vincent Chevrier. Robustness of Cellular Automata in the Light of Asynchronous Information Transmission
  Cellular automata are classically synchronous: all cells are simultaneously updated. However, it has been proved that perturbations in the updating scheme may induce qualitative changes of behaviours. This paper presents a new type of asynchronism, the beta-synchronism, where cells still update at each time step but where the transmission of information between cells is disrupted randomly. We experimentally study the behaviour of beta-synchronous models. We observe that, although many effects are similar to the perturbation of the update, novel phenomena occur. We particularly study phase transitions as an illustration of a qualitative variation of behaviour triggered by continuous change of the disruption probability beta.
• Silvio Capobianco and Tommaso Toffoli. Can anything from Noether's theorem be salvaged for discrete dynamical systems?
  The dynamics of a physical system is linked to its geometry by Noether's theorem, which holds under standard hypotheses such as continuity. We explore the existence of similar links for discrete systems. As a testbed, we take the Ising spin model with both ferromagnetic and antiferromagnetic bonds. We show that for this family of systems energy not only acts as a generator of the dynamics, but also is conserved when the dynamics is time-invariant as in Noether's theorem.
• Jürgen Dassow, Florin Manea and Bianca Truthe. On Normal Forms for Networks of Evolutionary Processors
  We prove that any recursively enumerable set can be generated by networks with evolutionary processors where the rules can be applied at an arbitrarily chosen position, the control is done by finite automata with at most three states, and the rule sets are singletons or the underlying graph is a complete graph. If one allows arbitrary underlying graphs and additional application of insertions and deletions only to the rightmost or the to leftmost position for some nodes, then the control can be restricted to automata with only one state.
• Jérôme Durand-Lose. Geometrical accumulations and computably enumerable real numbers
  Abstract geometrical computation involves drawing colored line segments (traces of signals) according to rules: signals with similar color are parallel and when they intersect, they are replaced according to their colors. Accumulations can be devised to accelerate the computation and provide, in a finite duration, exact analog values as limits. In the present paper, we show that starting with rational numbers for coordinates and speeds, the time of any accumulation is a c.e. (compu- tably enumerable) real number and moreover, there is a signal machine and an initial configuration that accumulates at any c.e. date. Similarly, we show that the spacial positions of accumulations are exactly the d-c.e. (difference of computably enumerable) real numbers.
• Joost Joosten and Adan Cabello. Hidden variables simulating quantum contextuality increasingly violate the Holevo bound
  In this paper we approach some questions about quantum contextuality with tools from formal logic. In particular, we consider an experiment associated with the Peres- Mermin square. The language of all possible sequences of outcomes of the experiment is classified in the Chomsky hierarchy and seen to be a regular language. Next, we make the rather evident observation that a finite set of hidden finite valued variables can never account for indeterminism in an ideally isolated repeatable experiment. We see that, when the language of possible outcomes of the experiment is regular, as is the case with the Peres-Mermin square, the amount of binary-valued hidden variables needed to de-randomize the model for all sequences of experiments up to length n grows as bad as it could be: linearly in n. We introduce a very abstract model of machine that simulates nature in a particular sense. A lower-bound on the number of memory states of such machines is proved if they were to simulate the experiment that corresponds to the Peres-Mermin square. Moreover, the proof of this lower bound is seen to scale to a certain generalization of the Peres- Mermin square. For this scaled experiment it is seen that the Holevo bound is violated and that the degree of violation increases uniformly.
• Viv Kendon, Angelika Sebald, Susan Stepney, Matthias Bechmann, Peter Hines and Rob Wagner. Heterotic Computing
  Non-classical computation has tended to consider only single computational models: neural, analog, quantum, etc. However, combined computational models can both have more computational power, and more natural programming approaches, than such 'pure' models alone. Here we outline a proposed new approach, which we term heterotic computing. We discuss how this might be incorporated in an accessible refinement-based computational framework for combining diverse computational models, and describe a range of physical exemplars (combinations of classical discrete, quantum discrete, classical analog, and quantum analog) that could be used to demonstrate the capability.
• Takahiro Kubota, Yoshihiko Kakutani, Go Kato and Yasuhito Kawano. A Formal Approach to Unconditional Security Proofs for Quantum Key Distribution
  We present an approach to automate Shor-Preskill style un- conditional security proof of QKDs. In Shor-Preskill's proof, the target QKD, BB84, is transformed into another QKD based on an entangle- ment distillation protocol (EDP), which is feasible for direct analysis. We formalized their method as program transformation in a quantum programming language, QPL. The transform is dened as rewriting rules which are sound with respect to the security in the semantics of QPL. We proved that rewriting always terminates for any program and that the normal form is unique under appropriate conditions. By applying the rewriting rules to the program representing BB84, we can obtain the corresponding EDP-based protocol automatically. We nally proved the security of the obtained EDP-based protocol formally in the quantum Hoare logic, which is a system for formal verication of quantum pro- grams. We show also that this method can be applied to B92 by a simple modication.
• Russell Martin, Thomas Nickson and Igor Potapov. Geometric Computations by Broadcasting Automata on the Integer Grid
  In this paper we introduce and apply a novel approach for self-organization, partitioning and pattern formation on the non-oriented grid environment. The method is based on the generation of nodal patterns in the environment via sequences of discrete waves. The power of the primitives is illustrated by giving solutions to two geometric problems using the broadcasting automata model arranged in an integer grid (a square lattice) formation. In this model automata cannot directly observe their neighbours' state and can only communicate with neighbouring automata through the non-oriented broadcast of messages from a finite alphabet. In particular we show linear time algorithms for: the problem of finding the centre of a digital disk starting from any point on the border of the disc and the problem of electing a set of automata that form the inscribed square of such a digital disk. Possible generalizations and applications of techniques based on nodal patterns and the construction of different discrete wave interference pictures are discussed in the conclusion.
• Radu Nicolescu and Huiling Wu. BFS Solution for Disjoint Paths in P Systems
  This paper continues the research on determining a maximum cardinality set of edge- and node-disjoint paths between a source cell and a target cell in P systems. We review the previously proposed solution [1], based on depth-first-search (DFS), and we propose a faster solution, based on breadth-first-search (BFS), which leverages the parallel and distributed characteristics of P systems. The runtime complexity shows that, in terms of P steps, our BFS solution performs better than the DFS solution. Further, empirical simulations show that the BFS solution is able to scale up on multi-core hardware.
• Primoz Pecar and Iztok Lebar Bajec. The key elements of logic design in ternary quantum-dot cellular automata
  The ternary Quantum-dot Cellular Automata (tQCA) were demonstrated to be a possible candidate for the implementation of a future multi-valued processing platform. Recent papers show that the application of the adiabatic pipelining can be used to solve the issues of the tQCA logic primitives. The architectures of the resulting tQCAs become similar to their binary counterparts and the physical design rules remain similar to those for the binary QCA domain. The design of complex processing structures is, however, usually based on logic design. The foundation of logic design is functionally complete set of elementary logic primitives (functions). The currently available tQCA logic primitives, i.e. tQCA majority gate and tQCA inverter gate, do not constitute a functionally complete set. We here present a tQCA implementation of the ternary characteristic functions, which together with the tQCA majority gate and the ternary constants constitute a functionally complete set according to multi-valued Post logic.
• Lukáš Petrů and Jiří Wiedermann. A Universal Flying Amorphous Computer
  Amorphous computers are systems that derive their computational capability from the operation of vast numbers of simple, identical, randomly distributed and locally communicating units. The wireless communication ability and the memory capacity of the computational units is severely restricted due to their minimal size. Moreover, the units originally have no identifiers and can only use simple communication protocols that cannot guarantee a reliable message delivery. In this work we concentrate on a so-called flying amorphous computer whose units are in a constant motion. The units are modelled by miniature RAMs communicating via radio. We design a distributed probabilistic communication protocol and an algorithm enabling a simulation of a RAM in finite time. The underlying algorithms make use of a number of original ideas having no counterpart in the classical theory of distributed computing. Our result is the first one showing computational universality of a flying amorphous computer.
• David Sears and Kai Salomaa. Extended Watson-Crick L Systems with regular trigger languages
  Watson-Crick Lindenmayer systems (L systems) add a control mechanism to ordinary L system derivations. The mechanism is inspired by the complementarity relation in DNA strings, and it is formally defined in terms of a trigger language (trigger, for short). In this paper we prove that Uni-Transitional Watson-Crick E0L systems with regular triggers can recognize the recursively enumerable (RE) languages. We also find that even if the trigger is nondeterministically applied and the number of its applications can be unbounded then the computational power does not change. In the case where the number of applications of the trigger is bounded we find that the computational power lies within the ET0L languages. We also find that Watson-Crick ET0L systems where the number of complementary transitions is bounded by any natural number are equivalent in expressive power.
• William Stevens. Computing with planar toppling domino arrangements
  A method for implementing Boolean logic functions using arrangements of toppling dominoes is described. Any desired combinational function can be implemented. A circuit constructed using this method has no timing or order constraints on its inputs and requires no out-of-plane bridges for passing one line of dominoes over another. Since it is built using toppling dominoes, a circuit can be used only once.
• Abuzer Yakaryilmaz and A.C. Cem Say. Computation with narrow CTCs
  We examine some variants of computation with closed timelike curves (CTCs), where various restrictions are imposed on the memory of the computer, and the information carrying capacity and range of the CTC. We give full characterizations of the classes of languages recognized by polynomial time probabilistic and quantum computers that can send a single classical bit to their own past. Such narrow CTCs are demonstrated to add the power of limited nondeterminism to deterministic computers, and lead to exponential speedup in constant-space probabilistic and quantum computation. We show that, given a time machine with constant negative delay, one can implement CTC-based computations without the need to know about the runtime beforehand.
• Luděk Žaloudek and Lukáš Sekanina. Increasing Fault-Tolerance in Cellular Automata-Based Systems
  In the light of emergence of cellular computing, new cellular computing systems based on yet-unknown methods of fabrication need to address the problem of fault tolerance in a way which is not tightly connected to used technology. This may not be possible with existing elaborate fault-tolerant cellular systems so we strive to reach simple solutions. This paper presents a possible solution for increasing fault-tolerance in cellular automata in a form of static module redundancy. Further, a set of experiments evaluating this solution is described, using triple and quintuple module redundancy in the automata with the presence of defects. The results show that the concept works for low intensity of defects for most of our selected benchmarks, however the ability to cope with errors can not be intuitively deduced as indicated on the example of the majority problem.