Further Technical Results
In the previous chapters we have systematically considered only two types of problems and results related to them: computability power (also looking for normal forms, from various points of view, especially in what concerns the number of membranes) and co
- PDF / 4,472,465 Bytes
- 38 Pages / 439.32 x 666.12 pts Page_size
- 44 Downloads / 177 Views
In the previous chapters we have systematically considered only two types of problems and results related to them: computability power (also looking for normal forms, from various points of view, especially in what concerns the number of membranes) and computability efficiency. However, in the membrane computing literature there are several directions of research which are different from the above two, some of them mathematically motivated, others having computer science motivations, and others aiming to get closer to reality (in two directions: to the living cell, and to possible applications). In the present chapter we briefly present some results from the first two categories, that is with mathematical or computer science motivations, while in the next chapter we will consider attempts to bring membrane systems closer to biology or to other areas where the paradigms of membrane computing seem to be useful.
8.1 Decidability Results We start with types of problems which are standard in formal language theory, in general, in computer science, but which we have not discussed up to now in the framework of membrane computing: decidability. There are several problems of this type which can be formulated for P systems of different types or for their sets of numbers or languages. Can we decide, for systems II from a given class X, whether or not N(II) (or L(II) in the case of stringobjects) is empty lfinite/infinite/semilinear lin a given family NFL, for F L a family of languages from the Chomsky or Lindenmayer hierarchy? Are two systems equivalent? Then, we have questions at the level of configurations: given an arbitrary configuration of a system II, does the computation starting from it ever halt? (This is a reformulation of the emptiness problem.) Is that configuration reachable from the initial configuration? More specific problems: is a specified membrane from a given configuration (taken as an initial configuration of computations) ever dissolved? Does it ever become empty I elementary? And so on, and so forth - both classic questions from language theory and specific questions. G. Păun, Membrane Computing © Springer-Verlag Berlin Heidelberg 2002
330
Further Technical Results
Of course, if a class X of systems is universal, then it is expected that all (non-trivial) questions about systems of type X and about their sets of numbers/languages are undecidable. Also, some results from language theory can be imported in the new framework: if the class X is not universal, but covers at least the power of context-free languages (in a constructive manner; that is, starting from a grammar we can effectively construct an equivalent P system from class X), then the decidability problems which have a negative answer for context-free languages have a negative answer also for the languages generated by systems of type X. We do not consider such possibilities here systematically, but we do consider two problems which are specific to P systems. The first problem asks whether or not a given membrane is ever dissolved. This is
Data Loading...
