Gedächtnisprotokoll FGI210-1

Aufgabe 1

TS1 und TS2 gegeben

1. L(TS1) und L(TS2) angeben

2. Produktautomaten TS3 konstruieren mit <math>Sync=(x,x) \forall x \in A</math>

3. L(TS3) "berechnen"

4. Gilt <math>L(TS3) = L(TS1) \cap L(TS2)</math> ? Falls ja, gilt dies sogar allgemein?

5.

Aufgabe X1

Algorithmus so ungefähr gegeben:

f(n)
{
v := 0
  for i=0 to n
  {
     v:=v+i;
  }
return v/n;
}

1. Welchen Ausdruck berechnet der Algorithmus für n>0?

2. Schätze die Zeit- und Platzkomplexität im uniformen Kostenmaß ab. 3. Schätze die Zeit- und Platzkomplexität im logarithmischen Kostenmaß ab.

Aufgabe X2

Kripke-Struktur gegeben.

Per CTL-Algorithmus soll geprüft werden, ob EGa gilt.

1. Markiere alle Zustände (+ dazugehörende Kanten), in denen a gilt

2. Markiere alle SZK und kennzeichne die nicht trivialen.

3. Falls EGa gilt, gib einen entsprechenden Pfad in an (<math>\omega</math>-regulärer Ausdruck). Wie berechnet der Algorithmus diesen Pfad?

Aufgabe X3

Per Induktion sollte gezeigt werden, dass für alle erreichbaren Markierungen in allen Plätzen m(p) > 0 gilt, unter der Vorraussetzung, dass m0(p) > 0 in allen Plätzen ist, und W~(t,p) > 0 für alle t und p gilt.

Aufgabe X4

Das Workflow-Netz aus Präsenzaufgabe 5.1 war gegeben.

1. Ist das angegebene Workflow Netz N korrekt? (mit Begründung!)

2. Gilt folgende Aussage: Ein Workflow-Netz ist korrekt gdw. sein Abschluss <math>\overline{N}</math> lebendig ist.

Außerdem gabs noch Aufgaben: Petrinetze (Startmarkierung als Vektor von Multimengen angeben, Folgemarkierungen berechnen, ...) Vektorielle Zeitstempel (in Graphen eintragen), BPA (Prozessgraphen zeichnen, Ableitung im Prozessgraphenkalkül, Reduktion mit den Axiomen), Bisimilarität, Paralleloperator und Prozessgraph in ACP