Pfadvektorlogik

Pfadvektorlogik ist eine formale Logik zur Modellierung und Prüfung von Pfaden in gerichteten Graphen. Sie verbindet die Vorstellung von Pfaden als Variablen mit Operatoren zur Bildung und zum Vergleich von Pfadvektoren und ermöglicht es, Eigenschaften zu formulieren, die sich auf Sequenzen von Knoten und Kanten beziehen.

Ein Modell besteht aus einem Graphen G = (V,E) mit optionalen Beschriftungen auf Kanten und gegebenenfalls Knoten. Pfade π werden als endliche Sequenzen von Knoten und Kanten verstanden. Die Sprache enthält Pfadvariablen, atomare Prädikate wie „π enthält Knoten v“ oder „Kante e gehört zu π“, sowie Operatoren wie Konkatentation π = π1 ∘ π2, Teilpfad-Beziehungen π1 ≤ π2 und die Bildung von Pfadvektoren π = (π1, …, πn). Mit Pfadvektoren lassen sich auch arithmetische oder relationale Einschränkungen formulieren, etwa Kombinationen von Teilpfaden, Pfadlängen |π| oder Einschränkungen auf simple Pfade.

Semantik: Eine Interpretation ordnet jeder Pfadvariablen π einen konkreten Pfad in G zu. Atomare Formeln werden nach der Zuordnung wahr oder falsch bewertet. Logische Verknüpfungen, Pfadoperatoren und Vektoroperationen definieren, wie komplexere Pfad-Eigenschaften ausgedrückt und geprüft werden. Die Semantik folgt im Wesentlichen einer Tarskischen Interpretation für Pfadvariablen und Pfadoperatoren.

Beispiele zeigen, wie Pfadverktorlogik genutzt wird, um Pfade zu beschreiben, die bestimmte Knotenfolgen treffen, obligatorische oder verbotene Knoten enthalten oder Pfade in mehreren Schritten vergleichen.

Beziehungen: Die Logik steht in Zusammenhang zu Logiken über Programme, Temporal- und Modallogik sowie zu Abfragesprachen für Pfadmuster in Graphdatenbanken. Anwendungen finden sich in der Modellprüfung, Netzwerkrouting-Policyprüfung und der Pfadanalytik in Graphen.