Formal Language Theoretic Models of Bio-Molecular Computation

The main objective of the project is twofold: to develop new concepts for bio-molecular computing, mainly for models based on DNA related structures (test tube systems) and for models in membrane computing, and to improve and sharpen some important existing results. Particular emphasis is planned to be put on examining the complexity aspects of the existing constructions: studying complexity measures of test tube systems and membrane systems including descriptional and computational complexity aspects. Due to the unconventional nature of bio-molecular computational tools, non-conventional complexity measures (which cannot be interpreted for the classical Turing machine model) are also taken into account.