Unconventional Computation and Natural Computation

1. Front Matter

   PDF

2. Invited Papers

   1. Asymptotic Dynamics of (Some) Asyncronous Cellular Automata

      • Enrico Formenti

      Pages 1-2

   2. Processes Inspired by the Functioning of Living Cells: Natural Computing Approach

      • Andrzej Ehrenfeucht, Grzegorz Rozenberg

      Pages 3-5

3. Regular Papers

   1. On the Power of Threshold Measurements as Oracles

      • Edwin Beggs, José Félix Costa, Diogo Poças, John V. Tucker

      Pages 6-18

   2. Size Lower Bounds for Quantum Automata

      • Maria Paola Bianchi, Carlo Mereghetti, Beatrice Palano

      Pages 19-30

   3. Population Protocols on Graphs: A Hierarchy

      • Olivier Bournez, Jonas Lefèvre

      Pages 31-42

   4. Spectral Representation of Some Computably Enumerable Sets with an Application to Quantum Provability

      • Cristian S. Calude, Kohtaro Tadaki

      Pages 43-54

   5. On the Power of P Automata

      • Erzsébet Csuhaj-Varjú, György Vaszil

      Pages 55-66

   6. Array Insertion and Deletion P Systems

      • Henning Fernau, Rudolf Freund, Sergiu Ivanov, Markus L. Schmid, K. G. Subramanian

      Pages 67-78

   7. Boolean Logic Gates from a Single Memristor via Low-Level Sequential Logic

      • Ella Gale, Ben de Lacy Costello, Andrew Adamatzky

      Pages 79-89

   8. Light Ray Concentration Reduces the Complexity of the Wavelength-Based Machine on PSPACE Languages

      • Sama Goliaei, Mohammad-Hadi Foroughmand-Araabi

      Pages 90-101

   9. Small Steps toward Hypercomputation via Infinitary Machine Proof Verification and Proof Generation

      • Naveen Sundar Govindarajulu, John Licato, Selmer Bringsjord

      Pages 102-112

   10. Secure Information Transmission Based on Physical Principles

       • Dima Grigoriev, Vladimir Shpilrain

       Pages 113-124

   11. Hypergraph Automata: A Theoretical Model for Patterned Self-assembly

       • Lila Kari, Steffen Kopecki, Amirhossein Simjour

       Pages 125-137

   12. Modeling Heart Pacemaker Tissue by a Network of Stochastic Oscillatory Cellular Automata

       • Danuta Makowiec

       Pages 138-149

   13. Reaction Systems Made Simple

       • Luca Manzoni, Antonio E. Porreca

       Pages 150-161

   14. Voting with a Logarithmic Number of Cards

       • Takaaki Mizuki, Isaac Kobina Asiedu, Hideaki Sone

       Pages 162-173

   15. Asynchronous Signal Passing for Tile Self-assembly: Fuel Efficient Computation and Efficient Assembly of Shapes

       • Jennifer E. Padilla, Matthew J. Patitz, Raul Pena, Robert T. Schweller, Nadrian C. Seeman, Robert Sheline et al.

       Pages 174-185

   16. Control Languages Associated with Tissue P Systems

       • Ajeesh Ramanujan, Kamala Krithivasan

       Pages 186-197

   17. Geometric Methods for Analysing Quantum Speed Limits: Time-Dependent Controlled Quantum Systems with Constrained Control Functions

       • Benjamin Russell, Susan Stepney

       Pages 198-208

This book constitutes the refereed proceedings of the 12th International Conference on Unconventional Computation and Natural Computation, UCNC 2013, held in Milan, Italy, in July 2013. The 30 papers (28 full papers, 8 poster papers, and 2 invited papers) were carefully reviewed and selected from 46 submissions. The topics of the volume include: quantum, cellular, molecular, neural, DNA, membrane, and evolutionary computing; cellular automata; computation based on chaos and dynamical systems; massive parallel computation; collective intelligence; computation based on physical principles such as relativistic, optical, spatial, collision-based computing; amorphous computing; physarum computing; hypercomputation; fuzzy and rough 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.

• DNA computing
• cellular automata
• regular languages
• secure computations
• simulation
• algorithm analysis and problem complexity

• Dipartimento di Informatica, Sistemistica e Communicazione, Università degli Studi di Milano-Bicocca, Milan, Italy

  Giancarlo Mauri

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano–Bicocca, Milano, Italy

  Alberto Dennunzio, Luca Manzoni

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Milano, Italy

  Antonio E. Porreca

Policies and ethics