Affiliations: Institute of Mathematics and Comp.Sc., Academy of
Sciences of Moldova, Str. Academiei 5, Chişinău, MD-2028, Moldova.
artiom@math.md | Faculty of Informatics, Vienna University of Technology,
Favoritenstr. 9, 1040 Vienna, Austria. marion@emcc.at | Faculty of Informatics, Vienna University of Technology,
Favoritenstr. 9, 1040 Vienna, Austria. rudi@emcc.at | LACL, Université Paris 12, 61,
av.Gén. de Gaulle, 94010, Créteil, France.
verlan@univ-paris12.fr
Note: [] Address for correspondence: Faculty of Informatics, Vienna
University of Technology, Favoritenstr. 9, 1040 Vienna, Austria
Abstract: We consider a new variant of the halting condition in P systems,
i.e., a computation in a P system is already called halting if not for all
membranes a rule is applicable anymore at the same time, whereas usually a
computation is called halting if no rule is applicable anymore in the whole
system. This new variant of partial halting is especially investigated for
several variants of P systems using membrane rules with permitting contexts and
working in different transition modes, especially for minimal parallelism. Both
partial halting and minimal parallelism are based on an arbitrary set of
subsets from the set of rules assigned to the membranes.
Keywords: computational completeness, halting, minimal parallelism, P systems, permitting context
