Sticker P System

Introduction

Kari et al. (1998) introduced a new computing model called sticker systems which are language generating devices based on the sticker operation. Sticker operation is a model of the techniques used by Adleman in his successful experiment of computing a Hamiltonian path in a graph by using DNA (Adleman, 1994).

DNA sequences are double stranded structures composed of four nucleotides A (adenine), C (cytosine), G (guanine) and T (thymine), paired A-T and C-G according to Watson-Crick complementarity. Two single stranded sequences are “glued” together (by hydrogen bonds) forming a double stranded DNA sequence only if one of the single stranded sequences is composed of the complementary nucleotides of the other. Informally, sticker operation is the operation of prolonging to the right of a sequence of (single or double) symbols by using given single stranded symbols, matching them with portions of the current sequence according to a complementarity relation. This operation can be used in building a generative or computing mechanism.

On the other hand, membrane computing introduced by Păun (2000) is a branch of natural computing, inspired from the structure and the functioning of living cells, as well as the organization of cells in tissues, organs and other higher order structures. The devices studied in membrane computing are called P systems, in the name of its introducer. P system is a non-deterministic distributed parallel model to deal mathematical or computational problems.

A basic P system has a cell-like membrane structure. The external membrane is called the skin membrane. A membrane without any other membrane inside is called elementary. Membranes delimit the space into several regions, where multisets of symbol-objects are placed. In each region, local evolution rules are applied in the form of multiset rewriting rules. These rules are applied in a synchronous maximally parallel way, non-deterministically choosing the rules and the objects. In a P system Π with m membranes, the m-tuple of multisets of objects present at any moment in the m-regions of Π determines the configuration of the system. Using the evolution rules one can define transitions among configurations. Any sequence of transitions starting from the initial configuration is called a computation. The computation is successful only if it halts (i.e., reaching a configuration where no rule can be applied). With this halting computation, a result is associated in the form of the multiplicity of objects placed in a specified membrane (called output membrane) or sent out of the system during the computation. More details about P system and its variants can be seen in Păun (2002) and Păun et al. (2010). Here Păun et al. (2010) is the most recent overview of the field of membrane computing.

In this work, a theoretical study about a variant called sticker P system is introduced. The motivation for this work is that P systems are powerful parallel computing devices and hence when we use sticker operations in P systems, the generative power is highly improved. Also, the number of steps in the computations will be less when compared with Sticker Systems.

The paper is organized as follows: In the first section some of the preliminaries are recalled. In the next section, the definition of sticker P system is introduced and the language generation power of such a system is investigated. The next section is a variant of this sticker P system is considered. Finally some concluding remarks are given.

Preliminaries

The set of non-negative integers is denoted by N. An alphabet V is a non-empty set, whose elements are called symbols. An ordered sequence of symbols is a string. The number of symbols in a string w is the length of the string, and is denoted by |w|. The empty string is denoted by λ. The set of strings of length n formed with symbols from the alphabet V is denoted by Vⁿ and A language over V is a subset of V* (i.e., L ⊆ V*). The family of languages that are regular is denoted by REG.

A multiset over an alphabet V is a mapping from V to N. It is represented by a string, say, w from V*, where the number of occurrences of a symbol a ∈ V in w gives the multiplicity of ‘a’ in the multiset associated with w. More notions and notations in formal languages can be seen in (Rozenberg & Salomaa, 2002).