Post on 13-Jan-2016
description
transcript
Fakultät für Informatik
Technische Universität Wien
Rudolf FREUND
Rechnen mit Molekülen
rudi@emcc.athttp://www.emcc.at/
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
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
• 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
• 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
• Medizinische Experten-/Diagnose-Systeme
• Telemedizin
• graphische Darstellung von NMR-Daten etc.
• Simulation biologischer Prozesse
• Drug Design
...
Bioinformatik und Computationale Biologie
European
EMCC
Molecular ComputingConsortium
Präsident: Grzegorz ROZENBERG (Leiden)
Österreichische Gruppe: Rudolf FREUND Franziska FREUNDMarion OSWALD Franz WACHTLER
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
Sticker Systems
„Dominoes“
Freund R., Păun Gh., Rozenberg G., Salomaa A., Bidirectional Sticker Systems, Pacific Symposium on Biocomputing '98, World Scientific, 1998.
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.
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.
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
--------------------------------------------------------------------------------
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.
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
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).
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
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,...)
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.
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
Test Tube Systems - Schema
Filter (i, F, j)
Tube i Tube j
Axiome i
Regeln i
Axiome j
Regeln j
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).
TTS – Reaktionen in den Test Tubes
Filter (i, F, j)
Tube i Tube j
Axiome i
Regeln i
Axiome j
Regeln j
TTS – Filtern und Wiederverteilen
Filter (i, F, j)
Tube i Tube j
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.
TTS – nächster Ableitungsschritt
Filter (i, F, j)
Tube i Tube j
Axiome i
Regeln i
Axiome j
Regeln j
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 .
When two tubes are enough
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.
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
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] �
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})
(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*.
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
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 { }.
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
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
(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/
1
2 3
4 5
Hautmembran
elementareMembran
Region
Membranstruktur [1 [2 [4 ]4 [5 ]5 ]2 [3 ]3 ]1
0: Umgebung
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.
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.
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
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
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.
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.
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).
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).
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.
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.
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)).
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.
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).
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 | |
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
► ...
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”;
DANKE
FÜR DIE AUFMERKSAMKEIT !