New Algorithms for Application of Evolution Rules based on Applicability Benchmarks.

Abstract

Abstract- Transition P System 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 consecutives configurations. Moreover, transitions between two consecutive configurations are provided by an exhaustive non-deterministic and parallel application of evolution rules inside each membrane of the P system. Hence, rules application is critical for the whole evolution process efficiency, because it is performed in parallel inside each membrane in each one of the evolution steps. The work presented here includes definitions of maximal and minimum applicability benchmarks of an evolution rule over a determined multiset of objects. These two definitions permit the design of new algorithms that improve complexity of traditional step by step one. This is achieved through new parallelism degree for the application of evolution rules.