Centre for Discrete Mathematics and

Abstract. The aim of these notes is to state a series of open problems and, mainly, research topics about P systems. They can be clustered in three classes: questions dealing with “classic ” topics in automata and language theory, questions motivated by the possible usefulness of P systems as computing models (implementation and complexity issues), and questions related to the fields where the P systems are inspired from, biology and biochemistry. Precise open problems can be found practically in all papers published or distributed so far on the web; here we are mainly interested in research directions, in classes of problems. A Wealth of Research Topics The reader is supposed to already be familiar with P systems, basic variants and basic results included, so I do not recall definitions, proofs, and theorems in a formal manner. The current bibliography of the domain, given at the end of this discussion, can be helpful to this aim. In particular, Chapter 3 from the monograph [P2] is recommended, as the first systematic survey of the domain (however, at the level of October 1999, which is not irrelevant for P systems study: several of the papers mentioned in the bibliography are dated later). I only recall the picture in Figure 1, illustrating the idea of a membrane structure, as well as a list of keywords, naming ingredients of P systems of various types: membrane, elementary membrane, skin membrane, membrane structure, label, region, oute