DCM on Friday, July 9th

09:00‑10:00 Session 1
Chair: Prakash Panangaden
Location: IF G.07A
09:00 Gordon Plotkin (University of Edinburgh)
Hierarchical Petri Nets
10:30‑12:30 Session 2
Chair: Barry Cooper
Location: IF G.07A
10:30 Luca Cardelli
Two-Domain DNA Strand Displacement

We investigate the computing power of a restricted class of DNA strand displacement structures: those that are made of double strands with nicks (interruptions) in the top strand, and with no protrusions. To preserve this structural invariant, we impose restrictions on the single strands they interact with: we consider only two-domain single strands consisting of one toehold domain and one recognition domain. We study fork and join signal processing gates based on these structures, and we show that these systems are amenable to formalization and to mechanical verification.

11:00 Miklos Bartha
Turing automata and graph machines

Indexed monoidal algebras are introduced as an equivalent structure for self-dual compact closed categories, and a coherence theorem is proved for the category of such algebras. Turing automata and Turing graph machines are defined by generalizing the classical Turing machine concept, so that the collection of such machines becomes an indexed monoidal algebra. On the analogy of the von Neumann data-flow computer architecture, Turing graph machines are proposed as potentially reversible low-level universal computational devices, and a truly reversible molecular size hardware model is presented as an example.

11:30 James Cheney
Causality and the Semantics of Provenance

Provenance, or information about the sources, derivation, custody or history of data, has been studied recently in a number of contexts, including databases, scientific workflows and the Semantic Web. Many provenance mechanisms have been developed, motivated by informal notions such as influence, dependence, explanation and causality. However, there has been little study of whether these mechanisms formally satisfy appropriate policies or even how to formalize relevant motivating concepts such as causality. We contend that mathematical models of these concepts are needed to justify and compare provenance techniques. In this paper we review a theory of causality based on structural models that has been developed in artificial intelligence, and describe work in progress on a causal semantics for provenance graphs.

12:00 A. Steven Younger and Emmett Redd
Computing by Means of Physics-Based Optical Neural Networks

We report recent research on computing with biology-based neural network models by means of physics-based opto-electronic hardware. New technology provides opportunities for very-high-speed computation and uncovers problems obstructing the wide-spread use of this new capability. The Computational Modeling community may be able to offer solutions to these cross-boundary research problems.

14:00‑15:00 Session 3
Location: IF G.07A
14:00 Russ Harmer (CNRS, Paris)
Rule-based Modeling: Theory and Practice
15:30‑18:00 Session 4
Location: IF G.07A
15:30 Vincent Danos and Nicolas Oury
Equilibrium and Termination

We present a reduction of the termination problem for a Turing machine (in the simplified form of the Post correspondence problem) to the problem of determining whether a continuous-time Markov chain (CTMC) presented as a set of Kappa graph-rewriting rules has an equilibrium. It follows that the problem of whether a computable CTMC is dissipative (ie does not have an equilibrium) is undecidable.

16:00 Damian Markham, Janet Anders, Michal Hajdusek and Vlatko Vedral
Measurement Based Quantum Computation on Fractal Lattices

In this presentation we extend on work which establishes an anaology between one-way quantum computation and thermodynamics to see how the former can be performed on fractal lattices. We find fractals lattices of arbitrary dimension greater than one which do all act as good resources for one-way quantum computation, and sets of fractal lattices with dimension greater than one all of which do not. The difference is put down to other topological factors such as connectivity. This work adds confidence to the analogy and highlights new features to what we require for universal resources for one-way quantum computation.

16:30 Janet Anders and Elisabeth Rieper
Continuous variable entanglement in biological systems

We consider a chain of harmonic oscillators with dipole-dipole interaction between nearest neighbours resulting in a van der Waals type bonding. The binding energies between entangled and classically correlated states are compared. We apply our model to DNA. Comparing our model with numerical simulations we argue that entanglement may play a crucial role in explaining the stability of the DNA double helix.

17:00 BenoƮt Valiron
Semantics of a Typed Algebraic Lambda-calculus

Algebraic lambda-calculi have been studied in various ways, but their semantics remain mostly untouched. In this paper we propose a semantical analysis of a general simply-typed algebraic lambda-calculus. We show how the languages of Vaux and Arrighi and Dowek fits in this framework. Then we study the problems arising from the addition of a fixed point combinator and how to modify the equational theory to solve them.

17:30 German Terrazas, Dario Landa-Silva and Krasnogor Natalio
Towards the Design of Heuristics by means of Self-Assembly

The current investigations on hyper-heuristics design have sprung up in two different flavours: heuristics that choose heuristics and heuristics that generate heuristics. In the latter, the goal is to develop a problem-domain independent strategy to automatically generate a good performing heuristic for the problem at hand. This can be done, for example, by automatically selecting and combining different low-level heuristics into a problem specific and effective strategy. Hyper-heuristics raise the level of generality on automated problem solving by attempting to select and/or generate tailored heuristics for the problem at hand. Some approaches like genetic programming have been proposed for this. In this paper, we explore an elegant nature-inspired alternative based on self-assembly construction processes, in which structures emerge out of local interactions between autonomous components. This idea arises from previous works in which computational models of self-assembly were subject to evolutionary design in order to perform the automatic construction of user-defined structures. Then, the aim of this paper is to present a novel methodology for the automated design of heuristics by means of self-assembly.