Die statische Struktur eines markierten Petrinetzes ist durch das Netz
selbst und die anfangliche Verteilung der Marken gegeben. Sein Verhalten
wird durch die Menge seiner Ablaufe oder durch seinen
Erreichbarkeitsgraphen beschrie- ben. Struktur und Verhalten hiingen eng
zusammenj so lassen sich dynamische Systemeigenschaften oft mit Hilfe
struktureller Methoden wie Deadlocks oder S-Invarianten beweisen. Fur
die Analyse eines markierten Petrinetzes auf dynamische Eigenschaften
reichen strukturelle Methoden dagegen meist nicht aus. So sind die
meisten dynamischen Eigenschaften -wie z.B. die Erreich-., barkeit einer
gegebenen Markierung - zwar entscheidbar, doch haben diese
Entscheidungsprobleme sehr groBe untere Komplexitatsschranken, die
wenig- stens dem Konstruktionsaufwand des Erreichbarkeitsgraphen
entsprechen. Eine effiziente Analyse basiert notwendigerweise auf der
Struktur eines mar- kierten Netzes. Sie ist also nur fur Netze moglich,
deren relevante dynamische Eigenschaften durch strukturelle
Eigenschaften charakterisiert werden. Fur Free-Choice-Petrindze wurde
Anfang der 70er Jahren von Fred Commoner (damals ein Student am MIT)
eine entsprechende Charakterisierung der dyna- mischen Eigenschaft
Lebendigkeit angegeben: ein Free-Choice-Netz ist genau dann lebendig,
wenn jeder Deadlock einen markierten Trap enthiilt. Leider ermoglicht
dieses Ergebnis aber keine effiziente Lebendigkeitsanalyse, denn das
Nicht-Lebendigkeitsproblem fur Free-Choice-Netze wurde als
NP-vollstandig nachgewiesen.
