24 Feb 2003 18:04:26 -0500

Related articles |
---|

Tarski's fixpoint theorem and static analysis -- reference? johnfl@cs.uoregon.edu (John Fiskio-Lasseter) (2003-02-24) |

Re: Tarski's fixpoint theorem and static analysis -- reference? Jens_Kilian@agilent.com (Jens Kilian) (2003-03-09) |

Re: Tarski's fixpoint theorem and static analysis -- reference? chase@theworld.com (David Chase) (2003-03-09) |

Re: Tarski's fixpoint theorem and static analysis -- reference? andrews@csd.uwo.ca (2003-03-14) |

Re: Tarski's fixpoint theorem and static analysis -- reference? johnfl@cs.uoregon.edu (John Fiskio-Lasseter) (2003-03-17) |

Re: Tarski's fixpoint theorem and static analysis -- reference? steck@stecksoft.com (Paul A. Steckler) (2003-03-23) |

From: | John Fiskio-Lasseter <johnfl@cs.uoregon.edu> |

Newsgroups: | comp.theory,comp.compilers |

Date: | 24 Feb 2003 18:04:26 -0500 |

Organization: | University of Oregon Computer Science Department |

Keywords: | theory, analysis, question |

Posted-Date: | 24 Feb 2003 18:04:26 EST |

I'm curious to know the earliest paper that identifies Tarski's theorem

regarding the existence of least/greatest fixpoints of monotonic

functions on a complete lattice ("A Lattice Theoretical Fixpoint

Theorem and its Applications", Pacific J. of Math. 5, 285-309, 1955) as

the basis for termination of the standard dataflow analysis algorithms.

None of the "classical" data flow works I've read (Killdall '73, Kam &

Ullman '76, Kam & Ullman '77, Hecht '77) cite this paper, nor any of

the compilers textbooks Ive seen (the dragon book, Fischer & LeBlanc,

Muchnick's _Advanced Compiler Design_).

It is, however, given an appendix' worth of summary in the recent

_Principles of Program Analysis_ textbook by Nielson, Nielson, &

Hankin, suggesting to me that his relevance was identified by the

abstract interpretation community. Indeed, the earliest citation of

Tarski's paper that I've seen (within the static analysis community) is

the Cousots' original abstract interpretation paper from POPL 77, and

they later published a constructive proof of Tarksi's theorem, also in

the Pacific Journal of Mathematics [82(1), 1979].

Were they the first ones to observe the relevance of Tarski's theorem

to static analysis, or is there an earlier paper that cites him?

Thanks,

John

----------------------------------------------------------------------

John Fiskio-Lasseter

* Phd. Student, CIS Dept., University of Oregon

* Deschutes 234 x6-1385 johnfl@cs.uoregon.edu

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.