Research Group on Natural Computing

Henry Adorna, Ph.D.

University of the Philippines Diliman

Abstract:
Gh. Paun and others suggested since at least five years, to consider communication complexity concepts in P systems. In this talk, we try to address this issue with several basic proposals. We consider the well-known Evolution-Communication P systems, introduced by Matteo Cavaliere in 2003 as our model of computation, but we put some constraint in doing communications. We introduce a so-called quanta of energy, that we require to have before any communication of an object be performed. Using this variant of P systems, we proposed a dynamical parameters as a more appropriate measures of communication complexity, namely, counting the communication steps or the number (and the weight) of communication rules used during the computation. These parameters can be used in three ways; as properties of P systems (considering the families of sets of numbers generated by systems with a given communication complexity), as conditions to be imposed on computations (accepting only those computations with a communication complexity bounded by a given threshold), and as standard complexity measures (defining the class of problems which can be solved by P systems with a bounded complexity). We ignore the evolution steps, in all three cases, hence it makes sense to consider hierarchies starting with finite complexity thresholds. We only give some preliminary results about these hierarchies (for instance, showing that already their lower levels contain complex e.g., non-semilinear sets), and we leave open many problems and research issues. We believe that our preliminary results indicate that this is a non-trivial research direction - especially if we desire to get close to the classic theory of communication complexity.

In some sense, the main aim of this talk is to call the attention to this research area, almost untouched in membrane computing, and we hope that colleagues will take this challenge and fill in this gap.

• Date: Thursday, 19th of November 2009, at 12:30
• Date: Thursday, 12th of November 2009, at 12:00 (DELAYED)
• Place: Seminar room of the department (ETS Ingeniería Informática (Avda. Reina Mercedes S/N, Sevilla), Module H, First floor)
• Language: English