Petrinetze, lineare Algebra und lineare Programmierung: Analyse, Verifikation und Korrektheitsbeweise von Systemmodellen: Teubner Texte zur Informatik, cartea 26

1 Einleitung.- 2 Definitionen und elementare Ergebnisse.- 2.1 Ungleichungssysteme.- 2.2 Petrinetze und Markierungen.- 2.3 Schaltfolgen.- 2.4 Die Inzidenzmatrix und die Markierungsgleichung.- 2.5 Markierte Netze und ihre Eigenschaften.- 2.6 Stelleninvarianten.- 2.7 Transitionsinvarianten.- 3 Erreichbarkeit von Markierungen.- 3.1 Entscheidung, Beweis und Widerlegung notwendiger Bedingungen.- 3.2 Lösbarkeit der Markierungsgleichung über ?.- 3.3 Lösbarkeit der Markierungsgleichung über ?.- 3.4 Lösbarkeit der Markierungsgleichung über ?+.- 3.5 Lösbarkeit der Markierungsgleichung über ?.- 3.6 Berechnung von Modulo-Stelleninvarianten.- 4 Fakten.- 4.1 Lineare Prädikate.- 4.2 Implikationen linearer Prädikate.- 4.3 Beweise von Fakten.- 4.4 Lebendigkeit und Verklemmungen.- 5 Fallen und Co-Fallen.- 5.1 Fallen und Erreichbarkeit.- 5.2 Fallen und lineare Prädikate.- 5.3 Co-Fallen.- 6 Ziele.- 6.1 Interne und externe Transitionen.- 6.2 Verifikation von Zielen.- 6.3 Verifikation bedingter Ziele.- 7 Die Rangbedingungen.- 7.1 Starke Schaltfolgen und stark lebendige Markierungen.- 7.2 Eine hinreichende Bedingung für die Existenz stark lebendiger Markierungen.- 7.3 Charakterisierung stark lebendiger Markierungen.- 7.4 Eine notwendige Bedingung für die Lebendigkeit von Markierungen.- 8 Anwendungen von Farkas Lemma.- 8.1 Analyse der Beschränktheit von Stellen.- 8.2 Überdeckbarkeit von Markierungen.- 8.3 Schalthäufigkeiten.- 8.4 Terminierung und Lebendigkeit.- 8.5 Abhängigkeit und Synchronieabstand.- Literatur.- Stichwortverzeichnis.

Sehr viele Analyseverfahren für Petrinetze verwenden die Inzidenzmatrix eines Netzes, die eine Verhaltensbeschreibung durch linear-algebraische Verfahren erlaubt. Das Buch gibt eine Einführung in derartige Verfahren und beschreibt vollständig und übersichtlich den State-of-the-art in diesem Bereich. Neben einer neuen systematischen Darstellung bekannter Konzepte runden etliche neue Ergebnisse das Thema ab. Es wird deutlich, daß dynamische Eigenschaften eines netzmodellierten Systems eng zusammenhängen mit der Lösbarkeit bzw. mit Lösungen von Gleichungs- und Ungleichungssystemen.Dabei werden sowohl ganzzahlige als auch rationale Lösungen betrachtet. Eine Differenzierung von Analyse, Verifikation und Beweis führt zu entsprechenden Verfahren, die sich sowohl im Algorithmentyp als auch in ihrer Komplexität unterscheiden. - Zum Verständnis des Buches sind außer Kenntnissen der üblichen mathematischen Terminologie keine Voraussetzungen notwendig. Ein Grundverständnis der Petrinetze ist jedoch hilfreich. Alle im Buch verwendeten Konzepte werden sorgfältig motiviert und mit Hilfe von Beispielen illustriert.