Introduction To Membrane Computing: Erzsébet Csuhaj-Varjú

Introduction to
Membrane Computing
Erzsébet Csuhaj-Varjú
Department of Algorithms and Their Applications,

Faculty of Informatics, Eötvös Loránd University
Pázmány Péter sétány 1/c, H-1117 Budapest, Hungary
[email protected]
Outline
 Membrane Computing
(bio-inspired computing, motivations, results,
applications)
 Membrane systems (P systems)

(the basic variant, computational power, size complexity)
 P systems with only communication

(symport/antiport P systems, universal antiport P
systems)
 Active P systems
(P systems with division, solving NP complete systems)
 Topics for future research

Bio-inspired Computational Models
Bio-inspired Models of Computation
Some Distributed Bio-Inspired
Computational Models
Membrane Systems (P systems)
Computational models abstracted from the

architecture and the functioning of the
living cell
(Gheorghe Paun, 1998)

Membrane systems – the cell
(The Oxford Handbook of Membrane Computing,

Gh. Paun, G. Rozenberg, A. Salomaa, eds., Oxford University Press, 2010)
A membrane structure
A hierarchical arrangement of regions where multisets
of objects evolve according to given evolutionary rules
Membrane systems, multiset rewriting rules
The rules
change the objects
move the objects between neighboring regions
The rules are applied

in parallel
in a synchronized manner
Computations by a membrane system
 The system starts in an initial configuration, and
evolves according to its rules,
 by changing, creating, deleting, and moving the

objects between the regions in parallel.
 Some of the evolutions/computations are defined to

be successful (no rule is applicable in any of the
regions, a final configuration is reached, etc.), and these
yield
 a result (a number or a vector of multiplicities of objects

in the regions)
P system – the basic variant
Example
(Paun, 2002)
P systems
 Main components  Other main

characteristics
 Objects  Type of rule
 Rules application
 Underlying graph  Mode of use
(generative,
(architecture) accepting)
 Type of result
Variants of P systems
 Objects: symbols, strings, spikes, arrays, trees, …

 Data structures: multisets, sets (languages)
 Location of objects: in the regions, on the
membranes, combined cases
 Form of rules: multisets of string rewriting rules,
(purely) communication rules, rules with membrane
creation, division, dissolution, spike processing, etc.
Variants of P systems - continued
 Control of application of rules: (catalysts),

priority, promoters, inhibitors, etc.
 Membrane configurations: cell-like (tree), tissue-like

(arbitrary graph), static or dynamic communication
channels (population P systems)
 Type of the membrane structure: static, dynamic,

precomputed
 Timing: synchronized, asynchronous, etc.

Variants of P systems - continued
 Application of rules:maximal parallelism,

minimal parallelism, bounded parallelism
 Successful computations:global halting,
local halting, etc.
 Modes of using the system: generating,
accepting
 Types of output: set of numbers, set of
vectors of numbers, languages, yes/no answer
Research Directions/Issues
 computing power, computational efficiency,

 descriptional complexity, normal forms, hierarchies,
 implementations,
 simulations,
 semantics, model checking, verifications,
 relations to dynamical systems
Types of Results
 universality, computational completeness
 collapsing hierarchies, infinite hierarchies,
 normal forms,
 polynomial solutions to NP-complete problems and even
to PSPACE-complete problems (with time/space
tradeoff),
 classifications, comparisons with Chomsky and
Lindenmayer hierarchies,
 comparisons with classic complexity classes, new
complexity classes
Types of Applications
 biology/biomedicine,
 population dynamics, ecosystems,
 economics,
 optimization,
 computer graphics,
 linguistics, natural language processing
 computer science,
 cryptography
Links to other models
 Petri nets,
 process algebra,
 X-machines,
 lambda calculus,
 ambient calculus, brane calculi
Coverage of the Domain
The Oxford Handbook of

Membrane Computing.
(Gh. Paun, G. Rozenberg, A. Salomaa,
eds.), Oxford University Press, Oxford,
2010.
P systems - the area
Standard features/characteristics:
distribution, communication, modularity,
dynamic change of structure, etc.
Unconventional features:
unbounded, massive parallelism,
properties which mimic properties of
natural systems.
Three basic models
 Symbol-object P systems (the basic model)
 Symport/antiport P systems (purely

communicating P systems)
 Active P systems (P systems with division)

Symbol-object P systems
Cell-like membrane systems operating with

multisets of objects and use
evolution and communication rules
Symbol-object P systems – the notion
Symbol-object P systems – variants
rule u->v
Cooperative, non-cooperative P system
|u|=1 – non-cooperative, |u|≥1 – cooperative P system

Symbol-object P systems – functioning
(w1,…,wm) – initial configuration
(w’1,…,w’m) – configuration
Configuration change:
by non-deterministic maximally parallel application of rules

(as many rules are applied simultaneously as possible in the P
system).
Symbol-object P systems – result of
computation
Computation: sequence of configurations starting from the initial

configuration
Successful computation: halting computation
Result of computation: the number of (vectors) of objects in

the output region at halting; or, the number of objects that
leave the system in a successful computation
Example
Rules:
Computed set of numbers:
Idea: # is used
for controlling the
computation
Symbol-object P systems - Notations
Some results
(flattening the P system)
(non-cooperation does not imply much power)
(cooperation results in the maximal power)

How to prove
Proof idea: (matrix grammar in Z-normal

form)
simulating P system
Basic extensions - dissolution
- after using this rule, the region is dissolving
Statement:
Proof idea:
E0L system
Simulating P system
Basic extensions – priorities among the rules
A system deciding
Whether k divides n
Symport/antiport P systems
Membrane systems with communication only

Symport/antiport rules
 Symport rule: (u,in) or (u,out)
 Antiport rule: (u,out;v,in)
u,v multisets
Symport/antiport P system
No new object is generated, objects can only be communicated

Symport/Antiport P system
Example
At the beginning, we put k copies of b into the skin membrane.

If k is not the power of 2, then the system never halts.
Computational Power
 Any computable set of numbers can be

obtained with a symport/antiport system with
9 membranes.
(Paun, Paun, 2002)
 The number of membranes or the size of

the rules can be decreased.
Computational Power
If the number of object-types (symbols) is

considered:
Computational Power
Variants with “tissue” structure

Symport/antiport systems can be
“programmed”
It is possible to
simulate a universal
register machine
The universal register machine has

a very small mumber of instructions
(Korec, 1996)
Universal antiport P systems
(Csuhaj-Varjú, Margenstern, Vaszil, Verlan, 2006)

Register Machines
Simulation of a decrement instruction
An antiport P system simulating a register
machine
The simulating register machine:

Universal antiport P systems
Variants of the result with different parameters:

Active Membrane Systems
One of the most important features of the cell is replication.
One type of replication is division (mitosis).

This way we are able to get 2n copies of the cell in n steps.
What about labels? Several membranes may have the same

label. (Labelling is not necessarily a one-to-one mapping.)
We also allow electrical charges of the membranes from the

set {+,-,0}, where 0 is the neutral polarization.
Configuration, Transition, Computation
Notation, Result
Solving SAT in linear time
Propositional formula in conjunctive
normal form
The SAT problem can be solved in linear time with

respect to the number of variables and the number
of clauses by a P system with active membranes
using rules of the forms (a), (b), (c),(e) (with 2-
divisions only).
Propositional formula
P system

Introduction To Membrane Computing: Erzsébet Csuhaj-Varjú

Uploaded by

Copyright:

Available Formats

Introduction To Membrane Computing: Erzsébet Csuhaj-Varjú

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Introduction To Membrane Computing: Erzsébet Csuhaj-Varjú

Uploaded by

Copyright:

Available Formats

Introduction to

Department of Algorithms and Their Applications,

 Membrane systems (P systems)

 P systems with only communication

 Topics for future research

Computational models abstracted from the

(Gheorghe Paun, 1998)

(The Oxford Handbook of Membrane Computing,

The rules are applied

 by changing, creating, deleting, and moving the

 Some of the evolutions/computations are defined to

 a result (a number or a vector of multiplicities of objects

 Main components  Other main

 Objects: symbols, strings, spikes, arrays, trees, …

 Control of application of rules: (catalysts),

 Membrane configurations: cell-like (tree), tissue-like

 Type of the membrane structure: static, dynamic,

 Timing: synchronized, asynchronous, etc.

 Application of rules:maximal parallelism,

 computing power, computational efficiency,

The Oxford Handbook of

 Symbol-object P systems (the basic model)

 Symport/antiport P systems (purely

 Active P systems (P systems with division)

Cell-like membrane systems operating with

Cooperative, non-cooperative P system

|u|=1 – non-cooperative, |u|≥1 – cooperative P system

(w1,…,wm) – initial configuration

by non-deterministic maximally parallel application of rules

Computation: sequence of configurations starting from the initial

Successful computation: halting computation

Result of computation: the number of (vectors) of objects in

Computed set of numbers:

(flattening the P system)

(non-cooperation does not imply much power)

(cooperation results in the maximal power)

Proof idea: (matrix grammar in Z-normal

- after using this rule, the region is dissolving

Membrane systems with communication only

 Symport rule: (u,in) or (u,out)

 Antiport rule: (u,out;v,in)

No new object is generated, objects can only be communicated

At the beginning, we put k copies of b into the skin membrane.

 Any computable set of numbers can be

 The number of membranes or the size of

If the number of object-types (symbols) is

Variants with “tissue” structure

The universal register machine has

(Csuhaj-Varjú, Margenstern, Vaszil, Verlan, 2006)

The simulating register machine:

Variants of the result with different parameters:

One of the most important features of the cell is replication.

One type of replication is division (mitosis).

What about labels? Several membranes may have the same

We also allow electrical charges of the membranes from the

The SAT problem can be solved in linear time with

You might also like