FB18 - Das Forum für Informatik

fb18.de / Diplom Informatik / Unterbereich Grundstudium / Formale Informatik

Paar Fragen zum F4 Skript

Paar Fragen zum F4 Skript 2006-05-22 16:09
Farcon
Ich arbeite mich gerade durch das F4 Skript und hab ein paar Fragen gesammelt.

1) Def. 4.28: Ein Auftragssystem AS=(A,<.) besteht aus einer endlichen Menge A von Aufträgen und einer irreflexiven, transitiven Relation
[img]http://mokrates.de/cgi-bin/texstring?%3C%20:=%20%3C.%5E+%20%5Csubset%20A%5E2%20[/img], wobei <. die direkten Präzedenzen beschreibt… (der Punkt bei <. steht jeweil im kleiner-als Zeichen).

Ich finde die Definition der Präzedenzrelation verwirrend. Die "normale" Präzedenzrelation ist <, die "direkte" ist <. ? Wir benutzen für das AS aber nur die direkte ? Heißt das Pluszeichen in <.+, dass die Relation transitiv sein soll ? In seinem Buch Rechensysteme steht die gleiche Definition nämlich etwas anders, "und einer irreflexiven, transitiven Relation
[img]http://mokrates.de/cgi-bin/texstring?%3C.%20%5Csubset%20A%5E2[/img]"


2)Die Definitionen S-Invarianten-Vektor ist
[img]http://mokrates.de/cgi-bin/texstring?i%20%5Cin%20%5Cmathbb%7BZ%7D%5ES%5Cbackslash%5C%7B0%5C%7D%0A%0A%[/img], für den T-Invarianten-Vektor
[img]http://mokrates.de/cgi-bin/texstring?j%20%5Cin%20%5Cmathbb%7BN%7D%5ET%5Cbackslash%5C%7B0%5C%7D[/img], warum ist der T-Invarianten-Vektor nicht aus Z wie der S-I-Vektor ?

3)Zur Definition Interpretation I eines schematischen Auftrags. Dort wird für eine Ausführungsfolge
[img]http://mokrates.de/cgi-bin/texstring?w=w_1w_2...w_%7B2n%7D%20%5Cin%20F_E(AS)[/img] eine Zustandsfolge
[img]http://mokrates.de/cgi-bin/texstring?d_0,d_1,...,d_%7B2n%7D[/img] definiert. Warum laufen diese Folgen bis 2n, und nicht nur bis n ?

4) In der Abbildung 3.19 gibt es eine Transition t1 die einen Guard "(x=a und y=rsa) oder (x=b und y=rsb)" hat. Die Transition besitzt aber nur einen Eingangplatz mit einer gefärbten Kante x. Heißt das der Guard setzt y auf rsa oder rsb, je nachdem ob x den Wert a oder b annimmt ? Kann ein Guard sowas ? Ich dachte der kann nur wahr oder falsch werden, also passiv sein.

5) Eher allgemein; existieren Auftragssysteme nur im F4 Skript ? Google spuckt dazu nix aus, und die einzig andere Quelle die ich dazu gefunden habe ist das Buch von Valk selbst.

Re: Paar Fragen zum F4 Skript 2006-05-22 17:08
Slater
2)
das eine war doch welche Transaktionen wie oft schalten müssen zum vorherigen Zustand
-> da können ja nur nichtnegative Zahlen rauskommen, 0 ist das mindeste (gar nicht schalten)

bei der anderen Invariante gehts um das Gegeneinanderaufrechnen von Stellen,
Stelle x + Stelle y - Stelle z = 15

-> da werden also nichtnegative Zahlen addiert und subtrahiert, deshalb braucht man Z

soweit ich mich erinnere/ eben schnell in alteren Topics nachgelesen habe ;)

Re: Paar Fragen zum F4 Skript 2006-05-23 02:59
georg
Ich arbeite mich gerade durch das F4 Skript und hab ein paar Fragen gesammelt.

1) Def. 4.28: Ein Auftragssystem AS=(A,<.) besteht aus einer endlichen Menge A von Aufträgen und einer irreflexiven, transitiven Relation
[img]http://mokrates.de/cgi-bin/texstring?%3C%20:=%20%3C.%5E+%20%5Csubset%20A%5E2%20[/img], wobei <. die direkten Präzedenzen beschreibt… (der Punkt bei <. steht jeweil im kleiner-als Zeichen).

Ich finde die Definition der Präzedenzrelation verwirrend. Die "normale" Präzedenzrelation ist <, die "direkte" ist <. ? Wir benutzen für das AS aber nur die direkte ? Heißt das Pluszeichen in <.+, dass die Relation transitiv sein soll ?

Damit soll gesagt werden, dass < die transitive Hülle von [img]http://mokrates.de/cgi-bin/texstring?%3C%5Ccdot[/img] sein soll.

In seinem Buch Rechensysteme steht die gleiche Definition nämlich etwas anders, "und einer irreflexiven, transitiven Relation
[img]http://mokrates.de/cgi-bin/texstring?%3C.%20%5Csubset%20A%5E2[/img]"

Dann vermute ich, dass das ein Tippfehler im Buch ist (ich glaube,
es gibt auch eine Stelle im Skript, wo er < und [img]http://mokrates.de/cgi-bin/texstring?%3C%5Ccdot[/img] vertauscht hat).

3)Zur Definition Interpretation I eines schematischen Auftrags. Dort wird für eine Ausführungsfolge
[img]http://mokrates.de/cgi-bin/texstring?w=w_1w_2...w_%7B2n%7D%20%5Cin%20F_E(AS)[/img] eine Zustandsfolge
[img]http://mokrates.de/cgi-bin/texstring?d_0,d_1,...,d_%7B2n%7D[/img] definiert. Warum laufen diese Folgen bis 2n, und nicht nur bis n ?

Nach Definition 4.30 (der die Bezeichnungen in Def. 4.34 entsprechen
sollen), hat A genau 2n Aufträge, nämlich s_1,…,s_n und l_1,…,l_n.

4) In der Abbildung 3.19 gibt es eine Transition t1 die einen Guard "(x=a und y=rsa) oder (x=b und y=rsb)" hat. Die Transition besitzt aber nur einen Eingangplatz mit einer gefärbten Kante x. Heißt das der Guard setzt y auf rsa oder rsb, je nachdem ob x den Wert a oder b annimmt ? Kann ein Guard sowas ? Ich dachte der kann nur wahr oder falsch werden, also passiv sein.

Ja und ja. [img]http://www.fb18.de/gfx/28.gif[/img] Der Guard kann nicht direkt bestimmen,
welche Belegung y bekommen soll, wenn x irgendeine Belegung
hat. Aber er kann festlegen, dass nur dann geschaltet werden
darf, wenn eine dieser Beiden Varianten eintritt. Also:
x=a und y=rsb wäre eine einwandfreie Belegung, aber mit ihr
kann nicht geschaltet werden, weil der Guard dann nicht
erfüllt ist.

5) Eher allgemein; existieren Auftragssysteme nur im F4 Skript ? Google spuckt dazu nix aus, und die einzig andere Quelle die ich dazu gefunden habe ist das Buch von Valk selbst.

Anscheinend. Ich habe auch schonmal recht lange nach
irgendwelcher Literatur dazu gesucht (weil ich eine
Literaturreferenz machen wollte), aber habe nichts gefunden.
Inhaltlich in eine ähnliche Richtung gehen manche Datenbank-
bücher, in denen etwas über Serialisierbarkeit steht
(z.B. Kemper und Eickler), aber die Auftragssysteme von
Herrn Valk sind wesentlich allgemeiner als die in diesen
Datenbankbüchern dargestellten Theorien (bei Kemper und
Eickler wird z.B. nicht nach Variablen differenziert,
sondern angenommen, dass je zwei Schreibaufträge
konfligieren (egal, welchen Speicher sie bearbeiten) und
somit ihre Reihenfolge in einer Serialisierung erhalten
bleiben muss, IIRC).

Re: Paar Fragen zum F4 Skript 2006-05-23 04:47
Viciarg
aber die Auftragssysteme von
Herrn Valk sind wesentlich allgemeiner als die in diesen
Datenbankbüchern dargestellten Theorien (bei Kemper und
Eickler wird z.B. nicht nach Variablen differenziert,
sondern angenommen, dass je zwei Schreibaufträge
konfligieren (egal, welchen Speicher sie bearbeiten) und
somit ihre Reihenfolge in einer Serialisierung erhalten
bleiben muss, IIRC).

Eigentlich ziemlich scheiße für ein Grundstudium, oder? Ich jedenfalls bin bei bei meiner Lernaktion auch derbe über diese AS gestolpert, weil es einfach _nichts_ darüber zu finden gab.