Symbolic model generation for graph properties

Auteurs

• Sven Schneider-Winden

Paramètres

• Mathématiques

En savoir plus sur le livre

Graphen sind in der Informatik allgegenwärtig, weshalb Methoden zur Darstellung und Untersuchung von Grapheigenschaften von großer Bedeutung sind. Besonders wichtig ist die vollautomatische Überprüfung der Erfüllbarkeit von Grapheigenschaften. In vielen Anwendungsszenarien ist es zudem wünschenswert, Graphen zu identifizieren, die bestimmte Eigenschaften erfüllen. Bei einer unendlichen Anzahl solcher Graphen ist ein kompakter Überblick anzustreben. Die Tableau-Methode für Grapheigenschaften von Lambers und Orejas ermöglicht die Entwicklung eines Algorithmus zur Generierung symbolischer Modelle. Grapheigenschaften werden in einer speziellen Logik formuliert, die auf Graphen und Graphmorphismen basiert und äquivalent zur First-Order Logic auf Graphen ist, wie sie von Courcelle eingeführt wurde. Der parallelisierbare Algorithmus ermittelt schrittweise eine endliche Menge symbolischer Modelle, wobei jedes Modell eine Menge endlicher Graphen beschreibt, die eine bestimmte Grapheigenschaft erfüllen. Diese Modelle gewährleisten Vollständigkeit, da sie alle endlichen Modelle abdecken, die die Eigenschaft erfüllen, und Korrektheit, da sie keine Graphen beschreiben, die die Eigenschaft verletzen. Zudem ist die Kompaktheit gegeben, da kein Modell von einem anderen abgedeckt wird. Der Algorithmus kann aus jedem symbolischen Modell ein minimales endliches Modell extrahieren und weitere endliche Modelle ableiten. Implementiert ist der Algor

Achat du livre

• Année de publication: 2017