55
Fakultät für Informatik Technische Universität Wien Rudolf FREUND Rechnen mit Molekülen [email protected] http://www.emcc.at/

Rechnen mit Molekülen

  • Upload
    lindley

  • View
    25

  • Download
    0

Embed Size (px)

DESCRIPTION

Rechnen mit Molekülen. Rudolf FREUND. [email protected]. http://www.emcc.at/. Fakultät für Informatik Technische Universität Wien. Überblick. Molecular Computing. ► DNA Computing. ● Watson-Crick, Sticker Systems ● Splicing, Cutting/Recombination ● Test Tube Systems. - PowerPoint PPT Presentation

Citation preview

Page 1: Rechnen mit Molekülen

Fakultät für Informatik

Technische Universität Wien

Rudolf FREUND

Rechnen mit Molekülen

[email protected]://www.emcc.at/

Page 2: Rechnen mit Molekülen

Molecular Computing

Überblick

► DNA Computing

► Membrane Computing

● Watson-Crick, Sticker Systems● Splicing, Cutting/Recombination● Test Tube Systems

● P-Systeme - ein allgemeines Modell

● Ausblick

● P-Systeme - ausgewählte Resultate

● P-Systeme - weitere Varianten/Modelle

Page 3: Rechnen mit Molekülen

NATURAL COMPUTING

1. Lerne von der Natur, um neue theoretische Modelle zu entwickeln (z.B. Computermodelle).

2. Verwende neue theoretische wissenschaftliche Erkenntnisse aus den Naturwissenschaften und ihren Anwendungsbereichen, um die (Vorgänge in der) Natur besser zu verstehen.

• Quantum Computing

• Molecular Computing

Page 4: Rechnen mit Molekülen

• ist eines der aktuellsten und sich am schnellsten entwickelnden Gebiete der Informatik

• vereint InformatikerInnen, BiologInnen, MedizinerInnen

• eröffnet neue Möglichkeiten für alle Bereiche:

► Computer helfen bei der - Entschlüsselung des menschlischen Genoms, - Simulation biologischer Prozesse, - Darstellung und Aufbereitung medizinischer Daten;

► InformatikerInnen lernen von der Natur; die größte Herausforderung: die gewonnenen theoretischen Erkenntnisse wieder in die Praxis umzusetzen, um damit zu einem besseren Verständnis biologischer Prozesse beizutragen.

Molecular Computing

Page 5: Rechnen mit Molekülen

• begann Oktober 1990, war auf 15 Jahre geplant • bereits 2 Jahre früher (2003) beendet Grund: rapider technologischer Fortschritt• Projektziele - Identifizierung aller Gene in menschlicher DNA (ca. 20000 - 25000), - Bestimmung der etwa 3 Milliarden Basispaare, - Speicherung dieser Informationen in Datenbanken, - Verbesserung der Methoden für die Datenanalyse, - Transferierung verwandter Technologien in den privaten Sektor, - Beachtung ethischer, juristischer, and sozialer Aspekte.

Human Genome Project

Page 6: Rechnen mit Molekülen

• Medizinische Experten-/Diagnose-Systeme

• Telemedizin

• graphische Darstellung von NMR-Daten etc.

• Simulation biologischer Prozesse

• Drug Design

...

Bioinformatik und Computationale Biologie

Page 7: Rechnen mit Molekülen

European

EMCC

Molecular ComputingConsortium

Präsident: Grzegorz ROZENBERG (Leiden)

Österreichische Gruppe: Rudolf FREUND Franziska FREUNDMarion OSWALD Franz WACHTLER

Page 8: Rechnen mit Molekülen

Watson-Crick-Komplementarität

Adenin(e)

Thymin(e)

Cytosin(e)

Guanin(e)

DNA DeoxyriboNucleic Acid

Doppelhelix

3´ … A T C G … 5´

5´ … T A G C … 3´

|| || ||| |||

DNS DeoxyriboNucleinSäure

Page 9: Rechnen mit Molekülen

Sticker Systems

„Dominoes“

Freund R., Păun Gh., Rozenberg G., Salomaa A., Bidirectional Sticker Systems, Pacific Symposium on Biocomputing '98, World Scientific, 1998.

Page 10: Rechnen mit Molekülen

Sticker Systems

Freund R., Păun Gh., Rozenberg G., Salomaa A., Bidirectional Sticker Systems, Pacific Symposium on Biocomputing '98, World Scientific, 1998.

Satz. Jede rekursiv aufzählbare Sprache L kann als Projektion einer von einem zweiseitigen Sticker-System erzeugten Sprache dargestellt werden.

Page 11: Rechnen mit Molekülen

Sticker Systems - Universalität

3´ … A T C G … 5´

5´ … T A G C … 3´

|| || ||| |||

Watson-Crick-Komplementarität entspricht Durchschnitt !

Durchschnitt zweier linearer Sprachen (lineare Grammatik mit Produktionen der Gestalt A → uBv, C → λ ),Projektion ergibt rekursiv aufzählbare Sprache.

Page 12: Rechnen mit Molekülen

DNA Splicing

3´ … A T C G … 5´

5´ … T A G C … 3´ || || ||| |||

3´ … A T C C … 5´

5´ … T A G G … 3

´

|| ||| sticky ends

3´ … T T C G … 5´

5´ … A A G C … 3´ || ||| sticky ends

3´ … T T C C … 5´

5´ … A A G G … 3´ || || ||| |||

splicing 1

splicing 2

recombination 2

recombination 1

--------------------------------------------------------------------------------

Page 13: Rechnen mit Molekülen

DNA Computing - SplicingSPLICING RULE r = u1 # u2 $ u3 # u4

x = x1 u1 u2 x2 , y = y1 u3 u4 y2 ,

SPLICING ( x , y ) r ( z , w )

z = x1 u1 u4 y2 , w = y1 u3 u2 x2

T. Head: Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviors. Bull. Math. Biology, 49 (1987), 737-759.

D. Pixton: Splicing in abstract families of languages. Theoretical Computer Science 234 (2000), 135-166.

E. Csuhaj-Varjú, R. Freund, L. Kari, Gh. Păun: DNA computing based on splicing: universality results. In: L. Hunter, T. Klein (Eds.): Pacific Symposium on Biocomputing '96, WSP (1996), 179-190.

Page 14: Rechnen mit Molekülen

SplicingSplicing: r = u1 # u2 $ u3 # u4 ,

x = x1 u1 u2 x2 , y = y1 u3 u4 y2 ,

( x , y ) r ( z , w )

z = x1 u1 u4 y2 , w = y1 u3 u2 x2

x1 u1 u2 x2

y1 u3 u4 y2

x1 u1 u4 y2

y1 u3 u2 x2

-------------------------------------------------------------------------------

x

y

z

w

Page 15: Rechnen mit Molekülen

Cut and Recombine (CR)CUTTING RULE u1 # [m] $ [n] # u2

RECOMBINATION RULE ( [m] , [n] )

x = x1 u1 u2 x2 , y = x1 u1 [m] , z = [n] u2 y2

CUTTING x r ( y , z )

x = x1 u1 u2 x2 , y = x1 u1 [m] , z = [n] u2 y2

RECOMBINATION ( y , z ) r x

R. Freund, F. Wachtler: Universal systems with operations

related to splicing. Computers and Art. Intelligence 15 (4).

Page 16: Rechnen mit Molekülen

Cut and Paste (CP)CUTTING RULE u1 # [m] c [n] # u2

PASTING RULE ( [m] , c , [n] )

x = x1 u1 c u2 x2 , y = x1 u1 [m] , z = [n] u2 y2

CUTTING x r ( y , z )

x = x1 u1 c u2 x2 , y = x1 u1 [m] , z = [n] u2 y2

PASTING ( y , z ) r x

Page 17: Rechnen mit Molekülen

Splicing Systems / CR/CP Systemsohne zusätzliche Mechanismen können nur

- unendlich viele Regeln

computationale Vollständigkeit (Universalität):

reguläre Sprachen erzeugt werden

- Multimengen

- periodische Regelmengen

- Test Tube Systems

- Membransysteme

- Kontrollmechnismen (Kontrollgraphen,...)

Page 18: Rechnen mit Molekülen

Test Tube Systems - LiteraturL. M. Adleman: Molecular computation of solutions to combinatorial problems. Science, 226 (Nov. 1994), 1021-1024.(lab solution of small travelling salesman problem)

E. Csuhaj-Varjú, L. Kari, and Gh. Păun: Test tube distributed systems based on splicing. Computers and Artificial Intelligence, Vol. 15 (2) (1996), 211-232.

R. Freund, E. Csuhaj-Varjú, and F. Wachtler: Test tube systems with cutting/recombination operations. In: R.B. Altman, A.K. Dunker, L. Hunter, T. Klein (Eds.):Pacific Symposium on Biocomputing '97 (1997), 163-174.

Page 19: Rechnen mit Molekülen

Test Tube Systems - Definition

= ( B , BT , n , A , , D , f )

• B Objekte

• BT B Terminalobjekte

• n Anzahl der Test Tubes

• A = ( A1 , ... , An ) Ai Axiome in Tube i

• = ( 1 , ... , n ) i Operationen in Tube i

• D Output/Input-Relationen der Gestalt ( i , F , j ) ; F ist ein Filter zwischen Tubes i und j

• f { 1 , ... , n } finaler Test Tube für Resultate

Page 20: Rechnen mit Molekülen

Test Tube Systems - Schema

Filter (i, F, j)

Tube i Tube j

Axiome i

Regeln i

Axiome j

Regeln j

Page 21: Rechnen mit Molekülen

TTS – Beginn eines Berechnungsschritts

Die Berechnungen im System gehen folgendermaßen vor sich:

Am Beginn der Berechnung werden die Axiome entsprechend der durch A vorgegebenen Verteilung

auf die n Test Tubes verteilt, d.h., Test Tube Ti

beginnt mit Ai. Ist nun Li der Inhalt von Test Tube Ti

am Beginn eines Ableitungsschrittes, dann operieren

die Regeln von auf Li und wir erhalten i*( Li).

Page 22: Rechnen mit Molekülen

TTS – Reaktionen in den Test Tubes

Filter (i, F, j)

Tube i Tube j

Axiome i

Regeln i

Axiome j

Regeln j

Page 23: Rechnen mit Molekülen

TTS – Filtern und Wiederverteilen

Filter (i, F, j)

Tube i Tube j

Page 24: Rechnen mit Molekülen

TTS - Wiederverteilung

Der nächste Teilschritt ist die Wiederverteilung

der Elemente von i*(Li) über alle Test Tubes

gemäß den entsprechenden Output/Input-

Relationen aus D, d.h., ist ( i,F,j) in D, dann

erhält der Test Tube Tj von i*(Li) nun i*(Li) F,

während der Rest von i*(Li), der nicht über

andere Test Tubes verteilt werden kann, in Ti

verbleibt.

Page 25: Rechnen mit Molekülen

TTS – nächster Ableitungsschritt

Filter (i, F, j)

Tube i Tube j

Axiome i

Regeln i

Axiome j

Regeln j

Page 26: Rechnen mit Molekülen

TTS – Resultat einer Berechnung

Das Resultat der Berechnungen in besteht aus allen

Objekten aus BT im finalen Test Tube.

Das Resultat der Berechnungen in könnte auch aus

allen Objekten aus B im finalen Test Tube bestehen,

d.h., in diesem Falle nehmen wir B = BT .

Page 27: Rechnen mit Molekülen

When two tubes are enough

Page 28: Rechnen mit Molekülen

TTS – Literatur

Rudolf Freund, Franziska Freund:

Test Tube Systems: When two tubes are enough.

DLT '99 and in: G. Rozenberg, W. Thomas (Eds.):

Developments in Language Theory,

Foundations, Applications and Perspectives.

WSP, Singapore (2000), 338-350.

Rudolf Freund, Franziska Freund:

Test Tube Systems or

How to Bake a DNA Cake.

Acta Cybernetica, Vol. 12, Nr. 4, 445-459.

Page 29: Rechnen mit Molekülen

TTS – Universalität mit CR

mit nur zwei Tubes und Filtern, die jeweils eine endliche Vereinigung von Mengen der Gestalt mW+n mit Markierungen m,n sind, erzeugt werden.

= (MW*M , [e]W+[f] , 2, (A1, Ø ) , (C1 R1 , C2), {(1, F1, 2) , (2, F2, 1)}, {2})

Beweis. Wir simulieren eine GrammatikG = (N,T,P,S) mit L(G) = L{d}, wobei d jeweils im letztenAbleitungsschritt in G erzeugt wird.

Ein Wort w wird durch rotierte Versionen [x]w2Bw1[y] ,w = w1w2 , repräsentiert. Terminalwörter sind von der Gestalt [e]w[f] , w T+.

Produktionen in P: p: mit 1 | | 2, 0 | | 2 .

V = N T {B} , W = V {d}.

Satz. Jede rekursiv aufzählbare Sprache L kannvon einem TTS mit CR-Regeln

Page 30: Rechnen mit Molekülen

TTS – Universalität mit CR (Beweis)M = {[e],[f],[e´],[f´], [x],[y],[x´],[y´]} { [lp], [rp], [lp´] |pLab}

{[xc],[yc],[xc´],[yc´] |cLab}

A1 = {[lp][y] |pLab, p:} {[x]c[xc´], [yc´] [y] |cV} {[x]BS[y]}

R1 = {([rp],[lp])|pLab} {([xc´], [xc] ), ([yc], [yc´]) |cV}

C1 = {u#[rp] $ [lp´]#[y] | uV, pLab, p:, ||=2}

{u#[rp] $ [lp´]#[y] | uV2 {B}, pLab, p:, ||=1}

C2 = {u#[yc] $ [y´]#c[y], [x]#[x´] $ [xc]#u | u,c V} {[x]B#[e´] $ [e]#u, u#[f] $ [f´]#d[y] | uT}

D = {(1, F1, 2), (2, F2, 1)}

F1 = [x]W+[y]

F2 = cV [xc]W+[yc] �

Page 31: Rechnen mit Molekülen

TTS – Universalität mit SplicingSatz. Jede rekursiv aufzählbare Sprache L kannvon einem TTS mit Splicing-Regeln

mit nur zwei Tubes und Filtern, die jeweils eine endliche Vereinigung von Mengen der Gestalt {A}W+{B} mit A,B W sind, erzeugt werden.

= (W*,{E}W+{F}, 2, (A1,A2), (R1 R2), {(1,F1,2),(2,F2,1)}, {2})

Page 32: Rechnen mit Molekülen

(Wort-)GrammatikenEine Grammatik G ist ein Konstrukt (N,T,P,S), ∙ N Nicht-Terminalsymbole; ∙ T Terminalsymbole, N ∩ T = { };

∙ P Produktionen der Gestalt u → v, u V*, v V+, wobei V := N T; ∙ S N Startsymbol (oder S V* Axiom).

Ableitungsrelation für u → v P definiert durch

xuy u→v xvy für alle x,y V*, was in Summe die

bekannte Ableitungsrelation G für G ergibt.

L(G) = { v T* | S G* v } .Sprachfamilie L(ARB): beliebige Produktionen; Sprachfamilie L(CF): kontextfreie Produktionen der Gestalt A → v mit A N und v V*.

Page 33: Rechnen mit Molekülen

Matrixgrammatiken

M eine endliche Menge endlicher Folgen von Produktionen aus P ist (ein Element von M heißt Matrix).

Für eine Matrix m(i) = [mi,1,…,mi,n(i)] in M und

v,u V* definieren wir v m(i) u genau dann wenn

w0,w1,…,wn(i) V* sowie w0 = v, wn(i) = u,

und für alle j, 1 ≤ j ≤ n(i), wj-1 m(i,j) wj gemäß G.

Eine Matrixgrammatik GM vom Typ X ist ein Konstrukt

Sprachfamilie L(X-MAT)

L(GM) = {v T* | w m(i,1) w1… m(i,k) wk,

wk = v, wj V*, m(i,j) M für 1 ≤ j ≤ k ,k ≥ 1}.

(N,T,P,M,w)wobei G = (N,T,P,w) eine Grammatik vom Typ X und

Page 34: Rechnen mit Molekülen

MultimengenEine Multimenge u <IN,V> ist eine Abbildung von V in IN,wobei IN die Menge der nicht-negativen ganzen Zahlen ist.

Eine Multimenge u <IN,V> kann auch durch das entsprechende Wort aus V* angegeben werden, das jedes Symbol aus V genau so oft enthält wie u oder, auch noch anders formuliert, durch ein Wort aus V*, dessen Parikh-Vektor den Koeffizienten von u entspricht:Multimenge <(a1,n1),...,(ak,nk)> entspricht

Parikh-Vektor (n1,...,nk) entspricht

Wort a1n1...ak

nk.

Wir betrachten auch Multimengen u <IN,V>,

wobei IN = IN { }.

Page 35: Rechnen mit Molekülen

Multimengen-GrammatikenEine Multimengen-Grammatik G ist ein Konstrukt (N,T,P,S), ∙ N Nicht-Terminalsymbole; ∙ T Terminalsymbole, N ∩ T = { }; ∙ P Produktionen der Gestalt u → v, u,v <IN,V>, u nicht die leere Multimenge; V := N T; ∙ S <IN,V> Axiom.

Ableitungsrelation für u → v P definiert durch

xu u→v xv für alle x <IN,V>, in Summe G für G.

L(G) = { v <IN,T> | S G* v } .Sprachfamilie Ps(ARB): beliebige Produktionen; Sprachfamilie Ps(CF): kontextfreie Produktionen der Gestalt A → v mit A N und v <IN,V>.Ps ... Parikh sets

Page 36: Rechnen mit Molekülen

eingeführt von Gheorghe PǍUN (1998)

- gaben der theoretischen Informatik neue Impulse, im Speziellen dem Gebiet der formalen Sprachen;

- abstrahieren Eigenschaften lebender Zellen;

- erlauben die Konstruktion verschiedenster Modelle universeller Computer,- eingeschränkte Modelle erlauben die Charakterisierung bekannter Sprachfamilien.

Membransysteme

Page 37: Rechnen mit Molekülen

(eingeführt von Gheorghe PǍUN , 1998)

MembranstrukturMultimengen von ObjektenEvolutions-/Kommunikations-Regeln angewendet • im maximal/minimal parallelen Modus• im sequentiellen/asynchronen Modus

Viele Varianten sind universell.Auflösung / Erzeugung von Membranen

P-Systeme (Membranysteme)

Gheorghe Păun: Membrane Computing - An Introduction. Springer-Verlag, Berlin, 2002.

The P Systems Web Page: http://ppage.psystems.eu/

Page 38: Rechnen mit Molekülen

1

2 3

4 5

Hautmembran

elementareMembran

Region

Membranstruktur [1 [2 [4 ]4 [5 ]5 ]2 [3 ]3 ]1

0: Umgebung

Page 39: Rechnen mit Molekülen

P-System - DefinitionEin P-System vom Typ X ist ein Konstrukt

= ( V,T, μ, wμ, Rμ, f),

- V/T Symbole/Terminalsymbole;

- μ Membranstruktur von ; üblicherweise werden die Membranen mit 1,...,n bezeichnet; die äußerste Membrane wird mit 1 markiert (Hautmembran);

- wμ ( = (w0,w1,...,wn) ) ordnet der Umgebung (w0) und

jeder Region innerhalb einer Membran i, 1 ≤ i ≤ n, eine initiale Multimenge über V zu (aus <IN,V>, üblicherweise sind aber alle wi, i>0, nur aus <IN,V>);

- Rμ ( = (R1,...,Rn) ) ordnet jeder Membran i, 1 ≤ i ≤ n,

von μ Regeln vom Typ X zu;- f Output-Membran, 1 ≤ f ≤ n.

Page 40: Rechnen mit Molekülen

P-System - RegelnEine Regel aus Ri in einem P-System ist von der Gestalt

Pa,Qa [ Pi,Qi | x [ u → v [ y.

Dabei werden die Multimengen x in der Region außerhalb der Membran i und u innerhalb der Membran i durch die Multimengen v bzw. y ersetzt („rewriting“), vorausgesetzt, alle in den Mengen Pa und Pi enthaltenen Multisets kommen in der Region außerhalb bzw. innerhalb der Membran i vor und keiner der in den Mengen Qa und Qi enthaltenen Multisets kommt in der Region außerhalb bzw. innerhalb der Membran i vor.

Page 41: Rechnen mit Molekülen

ist eines der gebräuchlichsten Merkmale vieler Modelle von P-Systemen, die bisher eingeführt wurden. Eine universelle Uhr, welche die parallele Anwendungder Regeln steuert, erscheint unrealistisch, ist aberfür viele interessante theoretische Resultat wichtig, speziell wenn es darum geht, Universalität zu beweisen und (NP-) harte Probleme zu lösen.

Im maximal parallelen Ableitungsmodus (max) wird eine Multimenge von Regeln derart ausgewählt, dass nach der Zuweisung entsprechender Objekte zu den (Kopien der) Regeln nicht genug Objekte mehr vorhanden sind, um noch die Anwendung einer zusätzlichen Regel zu erlauben.

maximal paralleler Ableitungsmodus

Page 42: Rechnen mit Molekülen

Im minimal parallelen Ableitungsmodus (min) wird eine Multimenge von Regeln derart ausgewählt, dass nach der Zuweisung entsprechender Objekte zu den Regeln nicht genug Objekte mehr vorhanden sind, um noch die Anwendung einer zusätzlichen Regel aus einer mit einer Membran assoziierten Regelmenge Ri, aus der noch keine

Regel verwendet wurde, zu erlauben.

minimal paralleler Ableitungsmodus

Page 43: Rechnen mit Molekülen

Sequentieller und asynchroner Ableitungsmodus

Biologische Prozesse in lebenden Organismen geschehen zwar parallel, aber nicht synchronisiert durch eine universelle Uhr.Viele Prozesse involvieren verschiedene Objekte gleichzeitig, aber die Prozesse selbst sind nicht synchronisiert.

Im sequentiellen Ableitungsmodus (seq) wird in jedem Ableitungsschritt genau eine Regel angewendet.

Im asynchronen Ableitungsmodus (asyn) wird in jedem Ableitungsschritt eine beliebige Anzahl von Regeln parallel angewendet.

Page 44: Rechnen mit Molekülen

P-System - Ableitung

Eine Ableitung im P system geschieht folgendermaßen:

Wir starten mit wi in der Umgebung und den Regionen

innerhalb der Membranen.

In jedem Ableitungsschritt werden die den Membranen zugeordneten Regeln gemäß dem Ableitungsmodus non-deterministisch ausgewählt und (parallel) angewendet.

Page 45: Rechnen mit Molekülen

P-System - Halten

Wir leiten im P system so lange ab bis eine bestimmte

Haltebedingung erfüllt ist:

- totales Halten (H): im gesamten System ist keine Regel

mehr anwendbar;

- partielles Halten (h): aus einer Menge Ri ist keine Regel

mehr anwendbar;

- adultes Halten (a): keine Konfigurationsänderung mehr;

- Halten mit Endzustand (s).

Page 46: Rechnen mit Molekülen

P-System – erzeugte Sprache

Alle terminalen Multimengen aus <IN,T>, die am Ende einer Ableitung in Membran f erscheinen, tragen zu der von erzeugten Menge von Multimengen Ps() bei.

Die Familie der von X-P-Systemen (mit Membranstruktur μ) im Ableitungsmodus m (seq, asyn, max, min) mit der Haltebedingung Y (H,h,a,s) erzeugten Mengen wird mit Ps((p,f)X-P,m,Y) bezeichnet. Sind alle Kontextbedingungen in einem X-P-System leer, dann bezeichnen wir die entsprechenden Mengenfamilien mit Ps(X-P,m,Y); sind nur erlaubte (“permitting contexts”) bzw. nur verbotene Kontextbedingungen vorhanden (“forbidding contexts”), d.h., alle Q-Mengen bzw. alle P-Mengen leer, dann bezeichnen wir die entsprechenden Mengenfamilien mit Ps(pX-P,m,Y) bzw. Ps(fX-P,m,Y).

Page 47: Rechnen mit Molekülen

P-Systeme – minimal paralleler Ableitungsmodus und partielles Halten

Satz. P-Systeme können in einer beliebigen Membranstruktur im sequentiellen, asynchronen undminimal parallelen Ableitungsmodus mit partiellem Halten nur Mengen von Multimengen erzeugen, die auch von kontextfreien Matrixgrammatiken erzeugten werden, d.h.,

Ps(X-P,{seq,asyn,min},h) = Ps(CF-MAT) = Ps(L(CF-MAT)).

R. Freund, M. Oswald: P systems with partial halting. 2007.

Page 48: Rechnen mit Molekülen

P-Systeme mit Kommunikationsregeln

Kommunikationsregeln (communication rules)

Antiport-Regeln der Gestalt (u,out;v,in) entsprechen Regeln v [ u → u[ v.

Symport-Regeln der Gestalt (u,out) bzw. (v,in)) entsprechen Regeln [ u → u[ bzw. v [ → [ v.

Page 49: Rechnen mit Molekülen

P-Systeme mit Kommunikationsregeln

Satz. P-Systeme mit Kommunikationsregeln (Antiport-und Symport-Regeln) können in einer beliebigen Membranstruktur im sequentiellen Ableitungsmodus nur Mengen von Multimengen erzeugen, die auchvon Matrixgrammatiken erzeugt werden, d.h.,

Ps(AntiSym-P( [1 ]1 ),seq,{H,h}) =

Ps(AntiSym-P,seq,{H,h}) = Ps(CF-MAT) = Ps(L(CF-MAT)).

Satz. P-Systeme mit Antiport- und Symport-Regeln können in nur einer Membran im maximal parallelen Ableitungsmodus jede rekursiv aufzählbare Menge von Vektoren nicht-negativer ganzer Zahlen erzeugen, d.h.,

Ps(AntiSym-P( [1 ]1 ),max,{H,h}) = Ps(L(ARB)).

Page 50: Rechnen mit Molekülen

P-Systeme für Wortsprachen

Satz. Jede rekursiv aufzählbare Sprache L kann von einem P-System mit verbotenem Kontext und kontextfreien Produktionen in einer Membranstruktur von zwei Membranen im sequentiellen Ableitungsmoduserzeugt werden, d.h. (f = forbidden context),

L(fCF-P( [1 [2 ]2 ]1,seq,H) ) = L(ARB).

R. Freund: P systems working in the sequential modeon Arrays and strings. DLT 2004, Dez. 2004, Auckland.

Page 51: Rechnen mit Molekülen

P-Systeme ohne verbotenen Kontext

Satz. Ohne verbotenen Kontext können P-Systeme mitkontextfreien Produktionen (in einer linearen Membranstruktur von drei Membranen) im sequentiellenAbleitungsmodus nur Sprachen erzeugen, die vonMatrixgrammatiken erzeugt werden, d.h.,

L((p)CF-P( [1 [2 [3 ]3 ]2 ]1 ),seq,H ) = L(CF-MAT).

Satz. Ohne Kontextbedingungen können P-Systeme mitkontextfreien Produktionen (in einer linearen Membranstruktur von drei Membranen) im maximal parallelen Ableitungsmodus jede rekursiv aufzählbare Sprache erzeugen, d.h.,

L(CF-P( [1 [2 [3 ]3 ]2 ]1 ) ,max,H) = L(ARB).

Page 52: Rechnen mit Molekülen

P-Systeme mit Splicing-RegelnSatz. Jede rekursiv aufzählbare Sprache L kann von einem P-System mit Splicing-Regeln mit nur einer Membran und sogar ohne Kontextbedingungen in den Regeln im sequentiellen Ableitungsmodus, erzeugt werden, d.h.,

L(splicingP( [1 ]1 ),seq,{H,h})= L(ARB).

| | Hautmembran | |

Axiome(unbeschränkt)

Axiome(unbeschränkt)

außen innen

| | Splicing-Regeln | |

Page 53: Rechnen mit Molekülen

Varianten von P-Systemen

u.A. verwendet für die Implementierung paralleler Algorithmen (üblicherweise linear in der Zeit), fürdie Lösung (NP-)harter Probleme

► Erzeugung/Auflösung von Membranen

► tissue(-like) P systemsbeliebige Graphstruktur für die Verbindung zwischen Zellen (nicht notwendigerweise ein Baum wie bei P-Systemen);z.B., zur Beschreibung neuraler Netzwerke

► ...

Page 54: Rechnen mit Molekülen

Ausblick► Untersuchung der Komplexität verschiedener Modelle von P-Systemen, vor allem im Hinblick auf die Grenze zwischen Universalität und Nicht-Universalität;

► (parallele) Algorithmen für die Lösung (NP-)harter Probleme basierend auf P-Systemen;

► Untersuchung des Potentials verschiedener Modelle von P-Systemen zur Beschreibung biologischer Prozesse;

► ...

► Implementierung verschiedener Modelle von P-Systemen “in silicio” und/oder “in vitro”;

Page 55: Rechnen mit Molekülen

DANKE

FÜR DIE AUFMERKSAMKEIT !