Research Group on Natural Computing

Speaker: Niall Murphy, Ph.D. (Polytechnic University of Madrid)

Abstract: Circuits are a well known example of a model of computation that is presented as families of finite computing devices with a uniformity condition on the entire family. Others include cellular automata, branching programs, etc. In a uniform family each input length is mapped to a single computing device that computes on the finite set of inputs of that length.

However, in the past 20 years there has been a number of "bio-inspired" computing models that favor a different approach. These models map each input to a computing device for that input; this scheme has been named semi-uniformity.

For many models it has been found that these notions are in fact the same, in the sense that the choice of uniformity or semi-uniformity
leads to characterisations of the same complexity classes. We have broken that trend by giving classes of uniform membrane systems that
are strictly weaker than their semi-uniform counterparts. In this talk we will give an update on our work on understanding the differences
between uniformity and semi-uniformity.

Information:

• Date: Thursday, 24-03-2011.
• Time: 11:30.
• Place: Seminar room of the department H1.50 (Module H, First floor, E.T.S. Ingeniería Informática)
• Language: English