Pfadlogik

Pfadlogik bezeichnet eine Gruppe formaler Sprachen und Semantiken, die darauf abzielen, Eigenschaften von Pfaden in Graphstrukturen, Zustandsübergangssystemen oder Programmlaufbahnen zu beschreiben. In der Praxis ermöglicht Pfadlogik Aussagen über das Vorhandensein oder die universelle Gültigkeit von Pfaden sowie über Eigenschaften, die entlang eines Pfades erfüllt sein sollen.

Syntax und Semantik: Typischer Aufbau umfasst Pfadvariablen, Prädikate für Knoten- bzw. Kanteneigenschaften und Operatorsymbole zur Verknüpfung von Pfaden (Konkatentation, Vereinigung, Kleene-Stern). Formeln verwenden Quantifizierer über Pfade, z. B. „Es existiert ein Pfad von Knoten a nach b, auf dem jeder betrachtete Knoten das Prädikat P erfüllt“ oder „Für alle Pfade ab a gilt schließlich Q“. Die Semantik basiert auf Modellen mit Knoten, Kanten und deren Beschriftungen; Pfade werden als Sequenzen von Knoten/ Kanten interpretiert, die den Pfadprädikaten entsprechen.

Beziehungen zu anderen Logiken: Pfadlogik steht in Verbindung mit Propositional Dynamic Logic (PDL), temporalen Logiken wie LTL/CTL sowie mit Abfragesprachen für Graphdaten (Regular Path Queries, RPQ) und Conjunctive Path Queries. In der Verifikation dient sie der Spezifikation von Eigenschaften entlang Pfaden, während sie in der Graphdatenanalyse als Abfragesprache genutzt wird.

Anwendungen und Grenzen: Sie findet Anwendung in der Programmanalyse, im Model Checking, in formalen Spezifikationen sowie in Datenbanken, die pfadbasierte Abfragen unterstützen. Die volle Ausdruckskraft moderner Pfadlogiken führt oft zu erhöhter Komplexität oder Unentscheidbarkeit, weshalb in der Praxis häufig beschränkte Fragmente verwendet werden.