Invited Talk
Networks of cell-like processors
Prof. Dr. Victor Mitrana
(Faculty of Mathematics and Computer Science, Univ. of Bucharest)

Place: Room 0S03 (Ground floor at the DSIC building in front of Secretariat)
Date: 23/10/2008
Time: 12:30
Abstract

Network of evolutionary processors (NEP) is a computing model inspired from cell biology; it consists of a network whose nodes are very simple processors able to perform just one type of point mutation (insertion, deletion or substitution of a symbol). These nodes are endowed with filters defined by some very simple context conditions. In a more general view, each node processor acts on the local data in accordance with some very simple predefined rules. Local data is then transmitted over the network following a given protocol. Only data which can pass a filtering process can be communicated. This filtering process may require to satisfy some conditions imposed by the sending processor, by the receiving processor or by both of them. All the nodes simultaneously send their data to and receive data from the nodes which they are connected to. A network of splicing processors (NSP) differs from a NEP by the operations accomplished by the nodes: splicing instead of point mutations. The computational power of these mechanisms is discussed. Then they are viewed as problem solvers and we give a characterization of the P and NP classes based on NEPs or NSPs. We also discuss universal NEPs and NSPs and compare their size complexity.