Computing with cells: membrane systems-some complexity issues

摘要: Membrane computing is a branch of natural which abstracts models from the structure and functioning living cell. The main ingredients membrane systems, called P are (i) structure, consists hierarchical arrangements membranes delimit compartments where (ii) multisets symbols, objects, evolve according to (iii) sets rules localised associated with compartments. By using in nondeterministic/deterministic maximally parallel manner, transitions between system configurations can be obtained. A sequence computation how evolving. Various ways controlling transfer objects one another applying rules, as well possibilities dissolve, divide or create have been studied. systems great potential for implementing massively concurrent an efficient way that would allow us solve currently intractable problems once future biotechnology gives practical bio-realization. In this paper we survey some interesting fundamental complexity issues such universality vs. nonuniversality, determinism nondeterminism, alphabet size hierarchies, characterizations context-sensitive languages other language classes various notions parallelism.