Processing math: 100%

Wiki

A universe of ideas

User Tools

Site Tools


uni:6:fsv:start

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
uni:6:fsv:start [2014-07-15 15:30] – [CTL] skrupellosuni:6:fsv:start [2020-11-18 18:11] (current) – external edit 127.0.0.1
Line 249: Line 249:
   * Fairness direkt angebbar: ''**(GF** p1.state=running**) =>** ...''   * Fairness direkt angebbar: ''**(GF** p1.state=running**) =>** ...''
   * CTL ist ausdrucksstärker   * CTL ist ausdrucksstärker
 +  * Für **alle** Pfade muss ... gelten
  
 ==== Büchi Automat ==== ==== Büchi Automat ====
Line 280: Line 281:
  
 ==== Datenflussgleichung ==== ==== Datenflussgleichung ====
-"Reichweite von Zuweisungen"+"Erreichbare Definitionen(Reachable Definitions)
  
-  * $RD_{exit}(\ell) = (RD_{exit}(\ell) \setminus \text{"Entwertete Zuweisungen"}) \cup \text{ "Neue Zuweisungen"}$ +  * $RD_{{\color{ForestGreen}entry}}(\ell) = \bigcup_{{\color{red}\ell'}:{\color{red}\ell'}\rightarrow\ell}RD_{exit}({\color{red}\ell'})$ 
-  * $RD_{entry}(\ell) = \bigcup_{\ell':\ell'\rightarrow\ell}RD_{exit}(\ell')$ +  * $RD_{exit}(\ell) = (RD_{{\color{ForestGreen}entry}}(\ell) \setminus \text{"Entwertete Zuweisungen"}) \cup \text{ "Neue Zuweisungen"}$ 
-  * Zu beginn werden //alle// Variablen mit "(X, ?)" initialisiert.+  * Zu beginn werden //alle// Variablen mit "$(X, \ell)$" initialisiert. 
 + 
 + 
 + 
 +"Verfügbare Ausdrücke" (Available Expressions) 
 +  * $AE_{{\color{ForestGreen}entry}}(\ell) = {\color{blue}\bigcap}_{{\color{red}\ell'}:{\color{red}\ell'}\rightarrow\ell}AE_{exit}({\color{red}\ell'})
 +  * AEexit()=(AEentry()killAE(B))genAE(B) 
 +  * killAE([x:=a])={Formeln, die x enthalten} 
 +  * genAE([x:=a])={Teilausdrücke von a ohne x} 
 +  * $gen_{AE}([bool\ exp]) = \{\text{Teilausdrücke von }bool\ exp\}
 +  * Zu beginn werden //alle// Variablen mit "" initialisiert. 
 +  * //Nur// Arithmetische Ausdrücke 
 + 
 + 
 +"Lebendige Variablen" (Live Variables) 
 +  * LVexit()=:LVentry() 
 +  * LVentry()=(LVexit()killLV(B))genLV(B) 
 +  * killLV([x:=a])={x} 
 +  * genLV([x:=a])={Variablen in a} 
 +  * genLV([bool exp])={Variablen in bool exp} 
 +  * Zu beginn werden //alle// Variablen mit "" initialisiert.
  
 ^ ^ RDentry() ^ RDexit() ^ ^ ^ RDentry() ^ RDexit() ^
Line 291: Line 312:
 | 3 | ... | ... | | 3 | ... | ... |
  
 +So lange ausfüllen, bis nichts mehr geht.
 +
 +Das geht, weil //Fixpunkte// und //Knaster-Tarski-Theorem//
 ==== SMV ==== ==== SMV ====
 Teile Teile
Line 392: Line 416:
 </code> </code>
  
 +===== Beweise =====
 +==== Vollständiger Verband ====
 +Verband (L,)
 +  * **reflexiv** \\ xL:xx
 +  * **transitiv** \\ x,y,zL:xyyzxz
 +  * **antisymetrisch** \\ x,yL:xyyxx=y
 +  * **Jede Teilmenge hat ein Supremum** \\ Jedes UL hat ein U
 +
 +==== Supremum ====
 +s=U
 +
 +  * **Ist obere Schranke** \\ xU:xs
 +  * **Ist //kleinste// obere Schranke** \\ s ist obere Schranke ss
 +
 +==== Monotonie ====
 +  * xyF(x)F(y)
 + 
 +==== Fixpunkt ====
 +  * x:F(x)=x
 +
 +Dazu muss F(x) monoton sein.
 ===== Probleme ===== ===== Probleme =====
 ==== Semaphor ==== ==== Semaphor ====
uni/6/fsv/start.1405431012.txt.gz · Last modified: 2020-11-18 18:10 (external edit)