Patrick Cousot, Abstract interpretation of graphs

Patrick Cousot.
Abstract Interpretation of Graphs
Pedro López-García, John P. Gallagher, and Roberto Giacobazzi (Eds.), LNCS 13160, Springer, 2023.

Paper: PDF (266 Kb)

Slides of the 25mn presentation at Manuel Hermenegildo's Festschrift: A4, 1 slide per landscape page, 753.6 Kb,

Keywords:
Abstract interpretation, Graph, Path problem, Shortest path, Minimum distance, Floyd-Roy-Warshall algorithm.

Abstract:
Path problems in graphs can be solved by abstraction of a fixpoint definition of all paths in a finite graph. Applied to the Roy-Floyd-Warshall shortest path algorithm this yields a naïve n⁴ algorithm where n is the number of graph vertices. By over-approximating the elementary paths and cycles and generalizing the classical exact fixpoint abstraction, we constructively derive the classical n³ Roy-Floyd-Warshall algorithm.

Bibliographic reference:

@inproceedings{Cousot-AVERTIS-2023,
  author    = {Patrick Cousot},
  title     = {Abstract Interpretation of Graphs},
  booktitle = {Analysis, Verification and Transformation for Declarative Programming and Intelligent Systems (AVERTIS)},
  year      = {2023},
  editor    = {Pedro López-García and John P. Gallagher and Roberto Giacobazzi},
  publisher = {LNCS 13160, Springer Nature Switzerland},
  pages     = {72--96},
}

copyright notice
Last modified: Thu May 18 09:38:49 EDT 2023