Patrick Cousot, Abstract interpretation of graphs

Patrick Cousot.
Abstract Interpretation of Graphs
Analysis, Verification and Transformation for Declarative Programming and Intelligent Systems (AVERTIS) , IMDEA Software, Madrid, Spain, Friday 29^th, 2019.
Slides of the 25mn presentation at Manuel Hermenegildo's Festschrift:
- A4, 1 slide per landscape page, 753.6 Kb,
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.
Keywords:
Abstract interpretation, Graph, Path problem, Shortest path, Minimum distance, Floyd-Roy-Warshall algorithm.

Bibliographic reference:

@inproceedings{CousotHalbwachsFest2018,
  author    = {Patrick Cousot},
  title     = {Abstract Interpretation of Graphs},
  booktitle = {Analysis, Verification and Transformation for Declarative Programming and Intelligent Systems (AVERTIS)},
  year      = {Friday November 29th, 2019},
  publisher = {IMDEA Software, Madrid, Spain},
 }

copyright notice
Last modified: Sun Dec 1 11:48:46 EST 2019