Unconventional Computation and Natural Computation: 18th International Conference, UCNC 2019, Tokyo, Japan, June 3–7, 2019, Proceedings (Theoretical Computer Science and General Issues)

This book constitutes the proceedings of the 18th International Conference on Unconventional Computation and Natural Computation, UCNC 2019, held in Tokyo, Japan, in June 2019. The 19 full papers presented were carefully reviewed and selected from 32 submissions. The papers cover topics such as hypercomputation; chaos and dynamical systems based computing; granular, fuzzy and rough computing; mechanical computing; cellular, evolutionary, molecular, neural, and quantum computing; membrane computing; amorphous computing, swarm intelligence; artificial immune systems; physics of computation; chemical computation; evolving hardware; the computational nature of self-assembly, developmental processes, bacterial communication, and brain processes. Preface Organization Abstracts of Invited Talks Deep Learning: Fundamentals, Challenges, and Applications On the Complexity of Self-assembly Tasks Construction of Molecular Swarm Robot Network Controllability: Algorithmics for Precision Cancer Medicine Co-Designing the Computational Model and the Computing Substrate (Invited Paper) Contents On the Complexity of Self-assembly Tasks References Co-Designing the Computational Model and the Computing Substrate 1 Introduction 2 When Does a Physical System Compute? 2.1 Abstraction/Representation Theory 2.2 Example: AR Theory Applied to Reservoir Computing 3 How Well Does a Physical System Compute? 3.1 How Well Does a Carbon Nanotube Reservoir Compute? 3.2 How Well Could a Carbon Nanotube Reservoir Compute? 3.3 How Well Do Other Substrates Compute? 4 How Well Does a Computational Model Fit? 5 Co-Designing Models and Substrates 6 Conclusion References Generalized Membrane Systems with Dynamical Structure, Petri Nets, and Multiset Approximation Spaces 1 Introduction 2 Preliminaries 2.1 Multiset Approximation Spaces 2.2 Generalized P Systems 3 Membrane Systems with Dynamically Changing Structure 3.1 Dynamical Structure Induced by the System of Base Multisets 3.2 Dynamical Structure Based on Membrane Boundaries 4 Concluding Remarks References Quantum Dual Adversary for Hidden Subgroups and Beyond 1 Introduction 2 Preliminaries 3 One-Matrix Problem 4 Substitute for 5 Discussion References Further Properties of Self-assembly by Hairpin Formation 1 Introduction 2 Basic Definitions 3 A New Solution to the CNF-SAT Using Hairpin Operations 4 Non-iterated Hairpin Formation and Semilinearity 5 Iterated Hairpin Formation and Semilinearity 6 Concluding Remarks References The Role of Structure and Complexity on Reservoir Computing Quality 1 Introduction 2 Reservoir Computing 3 CHARC Framework 4 Simulated Network Topologies 5 Experiment Parameter Settings 6 Results 6.1 Size and Structure 6.2 Directed vs. Undirected Networks 6.3 Parameters vs. Quality 7 Conclusion References Lindenmayer Systems and Global Transformations 1 Introduction 2 Global Transformations 2.1 A Structure for Locality 2.2 Respecting Locality 2.3 Designing Locality 2.4 Pattern Matching 2.5 Constructing the Result 3 Deterministic Lindenmayer Systems 3.1 D0L Systems 3.2 DIL Systems 4 D0L Systems as Global Transformations 4.1 The Category of Words WS 4.2 Designing the Rules of L 4.3 The Global Transformation L 5 DIL Systems as Global Transformations 6 Conclusion References Swarm-Based Multiset Rewriting Computing Models 1 Introduction 2 Preliminaries 3 Swarm-Based Models 3.1 Swarm System 3.2 Swarm Automaton 4 Introducing Position Information 5 Conclusion References DNA Origami Words and Rewriting Systems 1 Introduction 2 Preliminaries 3 DNA Origami Words and Rewriting Systems 3.1 DNA Origami Words 3.2 DNA Origami Rewriting Systems 3.3 Concluding Remarks References Computational Limitations of Affine Automata 1 Introduction 2 Preliminaries 2.1 Models 2.2 Cutpoint Languages 3 Logarithmic Simulation 4 A Non-affine Language References An Exponentially Growing Nubot System Without State Changes 1 Introduction 2 Model 3 System Construction 3.1 RIGHT_INSERT((A, B), L) 3.2 Doubling Insertion Sites 3.3 Handling Undesired Conditions 3.4 Expected Time 4 Conclusion and Discussion References Impossibility of Sufficiently Simple Chemical Reaction Network Implementations in DNA Strand Displacement 1 Introduction 2 Formalizing DNA Strand Displacement 3 The 2-r4 Condensed Reaction 4 Chemical Reaction Network Implementations 5 Discussion References Quantum Algorithm for Dynamic Programming Approach for DAGs. Applications for Zhegalkin Polynomial Evaluation and Some Problems on DAGs 1 Introduction 2 Preliminaries 3 Quantum Dynamic Programming Algorithm for DAGs 3.1 Functions for Vertices Processing 4 Quantum Algorithms for Evolution of Boolean Circuits with Shared Inputs and Zhegalkin Polynomial 5 The Quantum Algorithm for the Single Source Longest Path Problem for a Weighted DAG and the Diameter Search Problem for Weighted DAG 5.1 The Single Source Longest Path Problem for Weighted DAG 5.2 The Diameter Search Problem for a Weighted DAG References Viewing Rate-Based Neurons as Biophysical Conductance Outputting Models 1 Introduction 2 Background 2.1 Information Transfer Between Biological Neurons 2.2 Information Transfer in Simple Spiking Neuron Models 2.3 Information Transfer Between Firing-Rate Neuron Models 3 Portraying Rate-Based Neurons as Conductance-Outputting Models 3.1 Argument 1: Mathematical Equivalence 3.2 Argument 2: Artificial Firing-Rate Neurons Approximate Biological Conductance Models in Simulations 3.3 Argument 3: Synaptic Plasticity Models Using Discrete Spikes Don't Work Well 4 Discussion 4.1 Finding the Right Abstraction Level 4.2 Firing-Rates vs Conductance: Why the Perspective Matters 5 Future Work 6 Conclusion References The Lyapunov Exponents of Reversible Cellular Automata Are Uncomputable 1 Introduction 2 Preliminaries 3 Tilings and Undecidability 4 Uncomputability of Lyapunov Exponents 5 Conclusions References Geometric Tiles and Powers and Limitations of Geometric Hindrance in Self-assembly 1 Introduction 2 Preliminaries 2.1 Informal Description of the Abstract Tile Assembly Model 2.2 Informal Description of the Geometric Tile Assembly Model 2.3 Additional Models 2.4 Cooperation 2.5 Simulation 3 Simulation of Temperature-1 aTAM Systems 4 Glue Cooperation Cannot Be Simulated with Geometric Hindrance References DNA Computing Units Based on Fractional Coding Abstract 1 Introduction 2 Molecular Computing Units 2.1 M-OR Molecular Computing Unit 3 Simulation Results 3.1 DNA Pathway for M-OR Molecular Computing Unit 4 Conclusion Acknowledgement References The Role of the Representational Entity in Physical Computing 1 Introduction 2 AR Theory in a Nutshell 2.1 Our View of Physical Computing 2.2 Representation 2.3 -Commuting Diagrams 2.4 Compute Cycle 2.5 Generality of AR Theory 3 Including the RE in the Model 3.1 Overview 3.2 The Physical RE 3.3 The Physical RE in the Compute Cycle 4 Example: Intrinsic Computing in Bacteria 5 Conclusion References OIM: Oscillator-Based Ising Machines for Solving Combinatorial Optimisation Problems 1 Introduction 2 The Ising Problem and Existing Ising Machine Approaches 3 Oscillator-Based Ising Machines 3.1 Injection Locking in Oscillators 3.2 Global Lyapunov Function 3.3 Network of Coupled Oscillators Under SHIL and Its Global Lyapunov Function 3.4 Coupled Oscillator Networks with Frequency Variations 4 Examples 4.1 Small MAX-CUT Problems 4.2 MAX-CUT Benchmark Problems 4.3 A Graph Colouring Example 5 Conclusion References Relativizations of Nonuniform Quantum Finite Automata Families 1 Prelude: Background and Perspectives 1.1 Nonuniform State Complexity Classes 1.2 Relativizations of Finite Automata 1.3 Overview of Main Contributions 2 Fundamental Notions and Notation 2.1 Numbers, Strings, and Promise Decision Problems 2.2 Basics of Quantum Finite Automata 2.3 Oracle Mechanism and Turing Reducibility 3 Oracle Separations: Proofs of Theorems 1–3 3.1 Separations by Deterministic Oracles 3.2 Separations by Quantum Oracles 4 Turing Reducibility: Proofs of Theorems 4–5 4.1 Closure Properties 4.2 The Second Level of a Hierarchy 5 A Brief Discussion of Future Research References Self-stabilizing Gellular Automata 1 Introduction 2 Constraints on Gellular Automata 3 Gellular Automata Solving Maze Problems 3.1 Representation of Mazes and Solutions 3.2 Constructing Paths 3.3 Coping with Dead Ends 3.4 Coping with Loops 3.5 Self-stability 4 Leader Election 4.1 Outline 4.2 Detecting Multiple Leaders 4.3 Detecting Mismatch 4.4 Self-stability 5 Concluding Remark References Correction to: Geometric Tiles and Powers and Limitations of Geometric Hindrance in Self-assembly Correction to: Chapter “Geometric Tiles and Powers and Limitations of Geometric Hindrance in Self-assembly” in: I. McQuillan and S. Seki (Eds.): Unconventional Computation and Natural Computation, LNCS 11493, https://doi.org/10.1007/978-3-030-19311-9_16 Author Index