Patrick Cousot, Abstract interpretation of graphs

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

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 classicaln³ Roy-Floyd-Warshall algorithm.

Bibliographic reference:

@inproceedings{Cousot-AVERTIS-2021,
  author    = {Patrick Cousot},
  title     = {Abstract Interpretation of Graphs},
  booktitle = {Analysis, Verification and Transformation for Declarative Programming and Intelligent Systems (AVERTIS)},
  year      = {2021},
  editor    = {John P. Gallagher and Roberto Giacobazzi and Pedro López-García},
  note      = {to appear},
}

copyright notice
Last modified: Wed Aug 11 18:19:02 EDT 2021