Unconventional Computation and Natural Computation. 19th International Conference, UCNC 2021 Espoo, Finland, October 18–22, 2021 Proceedings

Preface
Organization
Abstracts of Invited Talks
Machine Materials
Programming RNA to Fold
Superconducting Quantum Computers
Computational Design of Nucleic Acid Circuits
Achieving Energy-Efficient Artificial Intelligence by Exploiting Imperfect Nanodevices
Contents
The Complexity of Multiple Handed Self-assembly
	1 Introduction
	2 Definitions
	3 Shape Building
		3.1 Separation
		3.2 Upper Bound for Building Sk
		3.3 Building Squares
	4 h-Hand Producibility
	5 h-Hand Unique Assembly Verification
		5.1 Membership
		5.2 Hardness: Reduction from k-ANTM
		5.3 Complexity
	6 Conclusion
	References
Computing with Magnetic Thin Films: Using Film Geometry to Improve Dynamics
	1 Introduction
	2 Reservoir Computing
	3 Magnetic Reservoir
	4 Benchmarks
	5 Film Geometry
		5.1 Experimental Setup
		5.2 Effect of Height:Width Ratio on Memory Capacity
		5.3 Effect of Height:Width Ratio on Task Performance
	6 Breaking Input Symmetry
		6.1 Experimental Setup
		6.2 Effect of Input Location on Memory Capacity
		6.3 Effect of Input Location on Task Performance
		6.4 Effect of Geometry and Input Location on Memory Capacity
	7 Conclusion
	References
Robust Real-Time Computing with Chemical Reaction Networks
	1 Introduction
	2 Preliminaries
	3 Lyapunov Reals Are Algebraic
	4 A Robust Notion of Memory in CRNs
	5 Discussion
	References
Zero-Knowledge Proof Protocol for Cryptarithmetic Using Dihedral Cards
	1 Introduction
		1.1 Zero-Knowledge Proofs for Puzzles
		1.2 Our Contribution
	2 Preliminaries: Dihedral Cards ch8ShinagawaTAMC2019,ch8ShinagawaNGCO2021
		2.1 Dihedral Cards
		2.2 Shuffle Operations on Dihedral Cards
		2.3 Protocols with Dihedral Cards
	3 Zero-Knowledge Proof Protocol for Cryptarithmetic
		3.1 How to Duplicate Commitment
		3.2 Procedure
	4 Evaluation
		4.1 Numbers of Cards and Shuffles
		4.2 Proof
	5 Conclusion
	References
Quantum Algorithm for Dyck Language with Multiple Types of Brackets
	1 Introduction
	2 Preliminaries
		2.1 Definitions
		2.2 Computational Model
	3 Quantum Algorithm
		3.1 Procedure for Step 1
		3.2 Procedure for Step 3
		3.3 Query Complexity
		3.4 The Overall Algorithm
	4 Future Work
		4.1 Generalizing Step 1
		4.2 Property Testing
		4.3 Tighter Bounds
	References
Affine Automata Verifiers
	1 Introduction
		1.1 The Computational Power of AfAs Compared to PFAs and QFAs
		1.2 The Verification Power of PFAs and QFAs
		1.3 Two-Way PFAs and QFAs
	2 Preliminaries
		2.1 Finite Automata with Deterministic and Affine States
		2.2 Affine Automata Verifiers
		2.3 Language Recognition/Verification and Classes
	3 Verification of Every Unary Language
	4  AMZ(AfA)
	5 Summary
	References
String Assembling Systems: Comparison to Sticker Systems and Decidability
	1 Introduction
	2 Preliminaries and Definitions
	3 Comparison of SAS with Sticker Systems
	4 Decidability
	5 Conclusion
	References
Fractal Dimension of Assemblies in the Abstract Tile Assembly Model
	1 Introduction
	2 Preliminaries
		2.1 The Abstract Tile Assembly Model
		2.2 Shapes and Fractals
	3 Sparsity
		3.1 Sparsity and -Dimension
		3.2 Sparsity of Discrete Self-similar Fractals
	4 Arbitrary Fractal Dimension Construction
		4.1 Construction Description
		4.2 Proof of Correct Fractal Dimension
	5 Conclusion
	References
Bistable Latch Ising Machines
	1 Introduction
	2 Background
		2.1 The Ising Model
		2.2 Latches
	3 Latch Ising Machines: A General Lyapunov Formulation
		3.1 Lyapunov Function
		3.2 Bistability Properties of the Generalized System; Lyapunov–Ising-Hamiltonian Relation
	4 Illustrative Examples
		4.1 Fully-Connected 3-Spin Graphs with Weights of Equal Magnitude
		4.2 G22 MAX-CUT Benchmark Problem
	5 Conclusion
	References
Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems
	1 Introduction
		1.1 Related Work
		1.2 Our Contribution
	2 Preliminaries
		2.1 Pile-Shifting Shuffle
		2.2 Sequence Selection Protocol
		2.3 Enhanced Matrix
		2.4 Double-Scramble Shuffle
		2.5 Rearrangement Protocol
		2.6 Neighbor Counting Protocol
	3 Verifying an Undirected Path
	4 Verifying a Connected Spanning Subgraph
	5 Proof of Correctness and Security
	6 Applications to NP-Complete Problems
		6.1 Hamiltonian Cycle Problem
		6.2 Maximum Leaf Spanning Tree Problem
		6.3 Bridges Puzzle
	7 Future Work
	A Copy and Arithmetic Protocols
		A.1 Copy Protocol
		A.2 Addition Protocol
		A.3 Multiplication Protocol
	References
Non-instantaneous Information Transfer in Physical Reservoir Computing
	1 Introduction
	2 The `Instantaneous' Equations
		2.1 The Original Form of the Reservoir Equations
		2.2 The Issue: Apparent Instantaneous Information Flow
		2.3 A Physically Reasonable Interpretation
		2.4 Pipelines of Reservoirs
	3 The `Physical' Equations
		3.1 Derived from Real-Time Interpretation
		3.2 Derived from Discretising Time in ODEs
		3.3 Delay Line Reservoir Formulation
	4 Consequences of Using the `Physical' Equations
		4.1 NRMSE Evaluation Measure
		4.2 Time Series Prediction Task: Sunspots
		4.3 Dynamical System Emulation Task: NARMA10
	5 Further Formulations of the `Physical' Equations
		5.1 Incorporating Output Feedback
		5.2 Multi-reservoirs with `Physical' Equations
	6 Conclusions
	References
Quantum Logical Depth and Shallowness of Streaming Data by One-Way Quantum Finite-State Transducers (Preliminary Report)
	1 Background, Motivations, and Challenges
	2 Preparation: Basic Notions and Notation
		2.1 Numbers, Sets, Languages, and Quantum States
		2.2 One-Way Quantum Finite-State Transducers with Garbage Tapes
		2.3 Description Sizes of 1dft's and 1qft's
	3 Basic Definitions
		3.1 Quantum Finite-State Compressors and Decompressors
		3.2 Quantum Finite-State Depth and Shallowness
	4 Major Contributions
		4.1 Basic Properties of QFSD-Complexity
		4.2 Subadditivity and Monotonicity Properties
		4.3 Depth/Shallowness of Infinite Sequences
	5 A Brief Closing Discussion
	References
Author Index