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: © 2011 |Pages: 14
DOI: 10.4018/jncr.2011070104
OnDemand PDF Download:
$37.50

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.
Article Preview

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 6: 2 Issues (2017): Forthcoming, Available for Pre-Order
Volume 5: 4 Issues (2015)
Volume 4: 4 Issues (2014)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing