Distributed models of molecular computation

Molecular computing is one of the modern areas of computer science aiming to perform computations by the use of biochemical processes. Although the idea of using DNA molecules as computing devices is not new, the real development of the field have started in 1994 after the famous experiment of L. Adleman in which he solved a small instance of the NP complete problem of finding a Hamiltonian path in a graph by manipulating test tubes containing DNA molecules.

Formal language theory plays an important role in the modeling of biochemical processes while the strands of DNA built by the four bases naturally correspond to words over a four letter alphabet and the sets of molecules naturally correspond to sets of words, that is, to languages. For the purpose of modeling chemical processes, there exist several language theoretic operations motivated by the recombinant behaviour of DNA strands, such as splicing, cutting/recombination, or other operations based on Watson-Crick complementarity. Based on these operations, distributed computational models like test tube systems or membrane systems have also been introduced. The aim of this research is to study the nature of these computational devices that are not only based on imitating biomolecular processes but also work in a distributed and parallel manner.