Benutzer:Ɯ/Überdeckungsgraph

Entwurf!

In der Petrinetzanalyse ist der Überdeckungsgraph ein endlicher Graph, der sich aus einem P/T-Netz berechnen läßt, und an dem sich gewisse Eigenschaften des Netzes ablesen lassen.

Definition

Ein Überdeckungsgraph von $N$ (adaptiert aus ) ist ein Graph, dessen Knotenmenge $S$ eine Überdeckungsmenge für das Netz $N$ darstellt, d.h. für jede im Netz erreichbare Markierung $m$ muß es in $S$ eine Pseudomarkierung geben, die $m$ repräsentiert. Die Kanten ergeben sich aus der Schaltregel des Netzes, wobei gilt: bei einer unendlichen Markierung ändert die Addition einer endlichen Zahl nichts.

Semantik

Ein $\omega$ bedeutet: es ist durch wiederholtes Durchlaufen eines Pfades im Graphen eine Markierung erreichbar, in der auf der $\omega$-Stelle beliebig viele Marken liegen.

Bedeutung

Mit dem Ü. läßt sich prüfen, ob ein Netz beschränkt ist.

Komplexität / Größe

Minimaler Überdeckungsgraph

Ein Überdeckungsgraph, der nach dem Karp-Miller-Algorithmus berechnet wurde, wird auch Karp-Miller-Graph (bei Karp und Miller allerdings noch "der Überdeckungsgraph") genannt. Dieser Graph ist im Allgemeinen nicht der kleinstmögliche Überdeckungsgraph. Der kleinstmögliche ist aber eindeutig bestimmt und kann berechnet werden.