Steffens, T: Kontextfreie Suche auf Graphen

David Melski und Thomas Reps haben Ende der Neunziger einen Algorithmus entwickelt, der es ermöglicht nach Knotenpaaren zu suchen zwischen denen ein Pfad existiert, der einer gegebenen kontextfreien Grammatik genügt. Dies ist beispielsweise dann interessant, wenn man einen Kontrollflussgraphen einer Applikation betrachtet und herausfinden möchte, ob alle von einem Prozess beanspruchten Ressourcen auch wieder frei gegeben werden. Da ein solcher Graph wegen der Methodenaufrufe im Normalfall eine geschachtelte Struktur aufweist, reicht ein Algorithmus, der mit einfachen Pfadbeschreibungen (wie einem regulären Ausdruck) arbeitet, nicht aus. Der Autor Tim Steffens überträgt den genannten Algorithmus auf weitere Problemstellungen, beweist seine Korrektheit, gibt Laufzeitabschätzungen und beschreibt Möglichkeiten der Optimierung. Um die Praxistauglichkeit zu zeigen, werden die Ergebnisse von Performanzmessungen einer Beispielimplementierung vorgestellt. Das Buch richtet sich an jeden, der sich für Software Technik und/oder Graphentheorie interessiert.