Published: 9th June 2010
DOI: 10.4204/EPTCS.26
ISSN: 2075-2180

EPTCS 26

Proceedings Sixth Workshop on
Developments in Computational Models: Causality, Computation, and Physics
Edinburgh, Scotland, 9-10th July 2010

Edited by: S. Barry Cooper, Prakash Panangaden and Elham Kashefi

Preface
S. Barry Cooper, Elham Kashefi and Prakash Panangaden
Understanding the Quantum Computational Speed-up via De-quantisation
Alastair A. Abbott and Cristian S. Calude
1
Landauer's principle in the quantum domain
Janet Anders, Saroosh Shabbir, Stefanie Hilt and Eric Lutz
13
Turing Automata and Graph Machines
Miklós Bartha
19
Engineering Long Range Distance Independent Entanglement through Kondo Impurities in Spin Chains
Abolfazl Bayat, Pasquale Sodano and Sougato Bose
33
Two-Domain DNA Strand Displacement
Luca Cardelli
47
Causality and the Semantics of Provenance
James Cheney
63
Equilibrium and Termination
Vincent Danos and Nicolas Oury
75
Algebraic characterisation of one-way patterns
Vedran Dunjko and Elham Kashefi
85
Quantum algorithms for testing Boolean functions
Dominik F. Floess, Erika Andersson and Mark Hillery
101
Measurement Based Quantum Computation on Fractal Lattices
Damian Markham, Janet Anders, Michal Hajdušek and Vlatko Vedral
109
Classification of delocalization power of global unitary operations in terms of LOCC one-piece relocalization
Akihito Soeda and Mio Murao
117
The space of measurement outcomes as a spectrum for non-commutative algebras
Bas Spitters
127
Towards the Design of Heuristics by Means of Self-Assembly
German Terrazas, Dario Landa-Silva and Natalio Krasnogor
135
Semantics of a Typed Algebraic Lambda-Calculus
Benoît Valiron
147
Computing by Means of Physics-Based Optical Neural Networks
A. Steven Younger and Emmett Redd
159
Open Graphs and Computational Reasoning
Lucas Dixon, Ross Duncan and Aleks Kissinger
169

Preface

Several new models of computation have emerged in the last few years, and many developments of traditional computational models have been proposed with the aim of taking into account the new demands of computer systems users and the new capabilities of computation engines. A new computational model, or a new feature in a traditional one, usually is reflected in a new family of programming languages, and new paradigms of software development.

DCM 2010, co-located with FLoC 2010, concerns Causality, Computation, and Physics, and aims to provide a forum for ideas about new computing means and models, with a particular emphasis on computational and causal models related to physics and biology. We believe that bringing together different approaches -- in a community with the strong foundational background characteristic of FLoC -- inevitably results in inspirational cross-boundary exchanges, and innovative further research.

Day two of this pre-FLoC 2010 workshop -- in the form of Quantum Information Science Scotland 2010 (QUISCO 2010) -- is given over to physics and quantum related computation. The content of day one is more typical of past DCM workshops -- covering a wide spectrum of topics related to the development of new computational models or new features for traditional computational models.

DCM 2010 attracted a full spectrum of excellent and innovative research papers, including twenty regular submissions and five invited talks. All the submissions were of a high quality, although scheduling constraints allowed just sixteen regular submissions to be accepted for presentation at the workshop. This volume contains the articles of fourteen of the talks presented, together with one from invited speaker Cristian Calude.

The co-chairs of DCM 2010 and QUISCO 2010 have many people to thanks for their help, including the DCM Steering Committee and the DCM 2010 Programme Committee (see below), and a number of external reviewers.

We would also like to thank the FLoC 2010 local organisers, and the FLoC Workshops Chair Philip Scott, for all their help with the organisation of DCM 2010.

Steering Committee

Programme Committee


S. Barry Cooper
Prakash Panangaden
(Co-chairs, DCM 2010)
and
Elham Kashefi
(Chair, QUISCO 2010)

June 2010