Algorithms Seminar

When: 7.5.2015 at 16:15 Where: B119/Kumpula

Abstract:
Tile assembly is a model of self-assembly of matter derived from Wang tilings. It has been implemented using DNA and gave rise to impressive experimental realizations, such as DNA Origami.

Tile assembly is computationally powerful: simulating Turing machines
is actually quite easy, but it requires a mecanism called
/cooperation/, by which tiles can sometimes assemble only if they
match at least two of their neighbors.

Without cooperation, this model seems much simpler: it assembles
paths with a finite number of tile types, and whenever a tile type
repeats along a path.

In one dimension (when assembling lines), we can use the "pumping
lemma" of finite automata. But in three dimensions (with cubes instead
of tiles), this model can simulate Turing machines.

In this talk, we show a pumping lemma for the two dimensional case,
finally showing the decidability of the model, which has been one of
the major open problems of the field for the last 15 years.

Host: Petteri Kaski