Teoria współbieżności

Informatyka

Laboratorium - Teoria śladów

Dane są:

• Alfabet A, w którym każda litera oznacza akcję.
• Relacja niezależności I, oznaczająca które akcje są niezależne (przemienne, tzn. można je wykonać w dowolnej kolejności i nie zmienia to wyniku końcowego).
• Słowo w oznaczające przykładowe wykonanie sekwencji akcji.

Zadanie:

Napisz program w dowolnym języku, który:

1. Wyznacza relację zależności D (1 p.)
2. Wyznacza postać normalną Foaty FNF([w]) śladu [w] (1.5 p.)
3. Wyznacza graf zależności w postaci minimalnej dla słowa w (1.5 p.)
4. Wyznacza postać normalną Foaty na podstawie grafu (1 p.)

Do zadania należy dostarczyć sprawozdanie, które będzie zawierać:

1. Opis programu z komentarzami
2. Wyniki działania dla przykładowych danych

Sprawozdanie wraz z kodem programu należy przysłać na adres balis [at] agh.edu.pl

Uwagi:

• Proszę wykorzystać algorytm ze str. 10 rozdziału Partial commutation and traces (pochodzi z Handbook of Formal Languages, Springer, 1997.
• Do rysowania grafu można wykorzystać Graphviz i format DOT. Wersja online: Webgraphviz.
• W p. 4 można użyć sortowania topologicznego.

Przykład:

Dla danych:

• (a) x := x + y
• (b) y := y + 2z
• (c) x := 3x + z
• (d) z := y - z.

• A = {a, b, c, d}
• I = {(a, d), (d, a), (b, c), (c, b)}
• w = baadcb

Wyniki:

1. D = {(a, a), (a, b), (a, c), (b, a), (b, b), (b, d), (c, a), (c, c), (c, d), (d, b), (d, c), (d, d)}
2. FNF([w]) = (b)(ad)(a)(bc)
3. Graf w formacie dot:

digraph g{
  1 -> 2
  2 -> 3
  1 -> 4
  3 -> 5
  4 -> 5
  3 -> 6
  4 -> 6
  1[label=b]  
  2[label=a]
  3[label=a]
  4[label=d] 
  5[label=b]
  6[label=c]
}

Dane testowe 2:

• A = {a, b, c, d, e, f}
• I = {(a, d), (d, a), (b, e), (e, b), (c, d), (d, c), (c, f), (f, c)}
• w = acdcfbbe

Dane testowe 3:

• Example 10 (str. 43) z Partial commutation and traces.