Evolution Rules Usefulness States Transition P System Sequential Machines Static Analysis
Issue Date:
2008
Publisher:
Institute of Information Theories and Applications FOI ITHEA
Abstract:
Transition P Systems are a parallel and distributed computational model based on the notion of the
cellular membrane structure. Each membrane determines a region that encloses a multiset of objects and
evolution rules. Transition P Systems evolve through transitions between two consecutive configurations that are
determined by the membrane structure and multisets present inside membranes. Moreover, transitions between
two consecutive configurations are provided by an exhaustive non-deterministic and parallel application of
evolution rules. But, to establish the rules to be applied, it is required the previous calculation of useful, applicable
and active rules. Hence, computation of useful evolution rules is critical for the whole evolution process efficiency,
because it is performed in parallel inside each membrane in every evolution step. This work defines usefulness
states through an exhaustive analysis of the P system for every membrane and for every possible configuration of
the membrane structure during the computation. Moreover, this analysis can be done in a static way; therefore
membranes only have to check their usefulness states to obtain their set of useful rules during execution.