Partial Halting and Minimal Parallelism Based on Arbitrary Rule Partitions

Issue title: Machines, Computations and Universality, Part I

Article type: Research Article

Authors: Alhazov, Artiom | Oswald, Marion | Freund, Rudolf | Verlan, Sergey

Affiliations: Institute of Mathematics and Comp.Sc., Academy of Sciences of Moldova, Str. Academiei 5, Chişinău, MD-2028, Moldova. [email protected] | Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria. [email protected] | Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria. [email protected] | LACL, Université Paris 12, 61, av.Gén. de Gaulle, 94010, Créteil, France. [email protected]

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

DOI: 10.3233/FI-2009-0031

Journal: Fundamenta Informaticae, vol. 91, no. 1, pp. 17-34, 2009