Elementary Active Membranes Have the Power of Counting

Elementary Active Membranes Have the Power of Counting

Antonio E. Porreca (Università degli Studi di Milano–Bicocca, Italy), Alberto Leporati (Università degli Studi di Milano–Bicocca, Italy), Giancarlo Mauri (Università degli Studi di Milano–Bicocca, Italy) and Claudio Zandron (Università degli Studi di Milano–Bicocca, Italy)
Copyright: © 2014 |Pages: 13
DOI: 10.4018/978-1-4666-4253-9.ch013

Abstract

P systems with active membranes have the ability of solving computationally hard problems. In this paper, the authors prove that uniform families of P systems with active membranes operating in polynomial time can solve the whole class of PP decision problems, without using nonelementary membrane division or dissolution rules. This result also holds for families having a stricter uniformity condition than the usual one.
Chapter Preview
Top

2. Preliminaries

We use P systems with restricted elementary active membranes, which are defined as follows.

Definition 1: A P system with restricted elementary active membranes of initial degree d ≥ 1 is a tuple Π = (Γ, Λ, μ, w1, …, wd, R), where:

  • •

    Γ is a finite alphabet of symbols (the objects);

  • •

    Λ is a finite set of labels for the membranes;

  • •

    μ is a membrane structure (i.e., a rooted unordered tree) consisting of d membranes enumerated by 1,…,d; furthermore, each membrane is labeled by an element of Λ, not necessarily in a one-to-one way;

  • •

    w1,…,wd are strings over Γ, describing the initial multisets of objects placed in the d regions of μ;

  • •

    R is a finite set of rules.

Each membrane possesses, besides its label and position in μ, another attribute called electrical charge (or polarization), which can be either neutral (0), positive (+) or negative (–) and is always neutral before the beginning of the computation.

Complete Chapter List

Search this Book:
Reset