Published: 15th November 2009
DOI: 10.4204/EPTCS.9
ISSN: 2075-2180

EPTCS 9

Proceedings Fifth Workshop on Developments in Computational Models —
Computational Models From Nature
Rhodes, Greece, 11th July 2009

Edited by: S. Barry Cooper and Vincent Danos
Preface
S. Barry Cooper and Vincent Danos
Algorithms for Quantum Branching Programs Based on Fingerprinting
Farid Ablayev and Alexander Vasiliev		1
Orthomodular Lattices Induced by the Concurrency Relation
Luca Bernardinello, Lucia Pomello and Stefania Rombolà		12
Circular Languages Generated by Complete Splicing Systems and Pure Unitary Languages
Paola Bonizzoni, Clelia De Felice and Rosalba Zizza		22
Random Constraint Satisfaction Problems
Amin Coja-Oghlan		32
A Type System for Required/Excluded Elements in CLS
Mariangiola Dezani-Ciancaglini, Paola Giannini and Angelo Troina		38
Deterministic Autopoietic Automata
Martin Fürer		49
Characterizing Polynomial Time Computability of Rational and Real Functions
Walid Gomaa		54
Rule-based Modelling and Tunable Resolution
Russ Harmer		65
An Intuitive Automated Modelling Interface for Systems Biology
Ozan Kahramanoğulları, Luca Cardelli and Emmanuelle Caron		73
Information Flow in Secret Sharing Protocols
Elham Kashefi, Damian Markham, Mehdi Mhalla and Simon Perdrix		87
Diffusion Controlled Reactions, Fluctuation Dominated Kinetics, and Living Cell Biochemistry
Zoran Konkoli		98
How Creative Should Creators Be To Optimize the Evolution of Ideas? A Computational Model
Stefan Leijnen and Liane Gabora		108

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. The aim of the DCM series of workshops is to bring together researchers who are currently developing new computational models or new features for traditional computational models, in order to foster their interaction, to provide a forum for presenting new ideas and work in progress, and to enable newcomers to learn about current activities in this area.

The special theme of DCM 2009, co-located with ICALP 2009, concerned Computational Models From Nature, with a particular emphasis on computational models derived from physics and biology. The intention was to bring together different approaches - in a community with a strong foundational background as proffered by the ICALP attendees - to create inspirational cross-boundary exchanges, and to lead to innovative further research. Specifically DCM 2009 sought contributions in quantum computation and information, probabilistic models, chemical, biological and bio-inspired ones, including spatial models, growth models and models of self-assembly. Contributions putting to the test logical or algorithmic aspects of computing (e.g., continuous computing with dynamical systems, or solid state computing models) were also very much welcomed.

In the event, DCM 2009 attracted a full spectrum of excellent and innovative research papers, including sixteen regular submissions and three invited ones. All the submissions were of a high quality, although scheduling constraints allowed just twelve regular submissions to be accepted for presentation at the workshop. This volume contains the articles of the eleven talks presented, together with one from invited speaker Amin Coja-Oghlan.

The workshop itself was exciting and enjoyable for all the participants, and there were many new and interesting interactions (at both scientific and social levels). The co-chairs have many people to thanks for their help, including the DCM Steering Committee and the DCM 2009 Programme Committee (see below), and a number of external reviewers, including: Manuel Campagnolo, Erzsebet Csuhaj-Varju, Simon Gay, Paola Giannini, Nick Papanikolaou, Nikolaos Siafakas, Mark-Oliver Stehr, Angelo Troina, Sergey Verlan, Maria Grazia Vigliotti, Martin Ziegler and Margherita Zorzi. We would also like to thank ICALP 2009 local organisers Christos Zaroliagis, Ioannis Chatzigiannakis, and Lena Gourdoupifor for all their help with the organisation of DCM 2009.

Steering Committee

Programme Committee