Unconventional models of computation: DNA and membrane computing.

摘要

The thesis investigates two areas of natural computing inspired from the biology of the living cell: DNA computing and membrane computing.; The main topic addressed in the first area mentioned above, DNA computing, is the power of splicing systems (currently called H systems) using splicing rules of a reduced complexity---with the complexity considered in the sense of the length of the sites where the cut-and-paste operations takes part. In this respect, the notion of the diameter of a splicing rule is introduced, and systematically investigated for several classes of H systems known to be computationally universal (able to generate all recursively enumerable languages): H systems with permitting or forbidding contexts, with target languages, with double splicing, working with multisets, distributed (with two cases: so called test tube systems, and time-varying H systems). Also pertaining to DNA computing is the study of some descriptional complexity measures (number of states, of transitions, etc.) defined for the so called Watson-Crick automata.; The second part of the thesis is devoted to membrane systems, both working with symbol-objects and with string-objects. Systems of the first type are the so-called symport/antiport P systems (used either in the standard mode, for generating a set of numbers, or in a new mode, which leads to a string associated with a computation: following the traces of certain objects through the membrane structure), the communicating P systems, the systems with active membrane (these systems are able to solve NP-complete problems in a polynomial time by making use of an exponential working space obtained by membrane division), and the tissue P systems. In what concerns the P systems with string-objects, we investigate both the case of rewriting rules (namely, used in the partially parallel manner) and the case of splicing rules---thus bridging the two main parts of the thesis.; Besides introducing several new notions (e.g., the diameter of an H system and new classes of P systems), investigating their properties, and improving a series of results from the literature, this thesis also formulates a series of open problems and re search topics. One also gives information about developments in DNA and membrane computing which have followed some of the investigations reported here.