Elementary Active Membranes Have the Power of Counting

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 Π = (Γ, Λ, μ, w₁, …, w_d, 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;

  • •

    w₁,…,w_d are strings over Γ, describing the initial multisets of objects placed in the d regions of μ;

  • •

    R is a finite set of rules.