Chaotic fixpoint iteration guided by dynamic dependency

Niels Jørgensen

Chaotic fixpoint iteration guided by dynamic dependency

Niels Jørgensen

Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › peer review

Abstract

An algorithm for abstract interpretation of logic programs is defined and analyzed. The algorithm is proved to be correct with respect to an abstract semantics for (a variant of) Prolog. This abstract semantics associates a given program with a function that maps each call pattern for a predicate to a distinct success pattern. The proposed algorithm employs a variant of chaotic iteration, and is based on what may be termed a dynamic dependency relation. A low worst-case complexity is achieved: the number of passes of dataflow analysis over each program clause is proved to be independent of the size of the rest of the program.

Originalsprog	Engelsk
Titel	WSA'93 : Proceedings of the Third International Workshop on Static Analysis
Redaktører	Patrick Cousot, Moreno Falaschi, Gilberto Filé, Antoine Rauzy
Antal sider	18
Forlag	Springer
Publikationsdato	sep. 1993
Sider	27-44
ISBN (Elektronisk)	978-3-540-57264-0
Status	Udgivet - sep. 1993
Udgivet eksternt	Ja
Begivenhed	3rd International Workshop on Static Analysis - Padova, Italien Varighed: 22 sep. 1993 → 24 sep. 1993 Konferencens nummer: 3

Konference

Konference	3rd International Workshop on Static Analysis
Nummer	3
Land/Område	Italien
By	Padova
Periode	22/09/1993 → 24/09/1993

Adgang til dokumentet

https://dl.acm.org/doi/10.5555/647164.717828

Andre filer og links

https://researchr.org/publication/sas%3A1993

Citationsformater

@inproceedings{db240e560bc24b34bf42f94b103623a3,

title = "Chaotic fixpoint iteration guided by dynamic dependency",

abstract = "An algorithm for abstract interpretation of logic programs is defined and analyzed. The algorithm is proved to be correct with respect to an abstract semantics for (a variant of) Prolog. This abstract semantics associates a given program with a function that maps each call pattern for a predicate to a distinct success pattern. The proposed algorithm employs a variant of chaotic iteration, and is based on what may be termed a dynamic dependency relation. A low worst-case complexity is achieved: the number of passes of dataflow analysis over each program clause is proved to be independent of the size of the rest of the program.",

author = "Niels J{\o}rgensen",

year = "1993",

month = sep,

language = "English",

pages = "27--44",

editor = "Patrick Cousot and Moreno Falaschi and Gilberto Fil{\'e} and Antoine Rauzy",

booktitle = "WSA'93",

publisher = "Springer",

note = "3rd International Workshop on Static Analysis, WSA 1993 ; Conference date: 22-09-1993 Through 24-09-1993",

}

TY - GEN

T1 - Chaotic fixpoint iteration guided by dynamic dependency

AU - Jørgensen, Niels

N1 - Conference code: 3

PY - 1993/9

Y1 - 1993/9

N2 - An algorithm for abstract interpretation of logic programs is defined and analyzed. The algorithm is proved to be correct with respect to an abstract semantics for (a variant of) Prolog. This abstract semantics associates a given program with a function that maps each call pattern for a predicate to a distinct success pattern. The proposed algorithm employs a variant of chaotic iteration, and is based on what may be termed a dynamic dependency relation. A low worst-case complexity is achieved: the number of passes of dataflow analysis over each program clause is proved to be independent of the size of the rest of the program.

AB - An algorithm for abstract interpretation of logic programs is defined and analyzed. The algorithm is proved to be correct with respect to an abstract semantics for (a variant of) Prolog. This abstract semantics associates a given program with a function that maps each call pattern for a predicate to a distinct success pattern. The proposed algorithm employs a variant of chaotic iteration, and is based on what may be termed a dynamic dependency relation. A low worst-case complexity is achieved: the number of passes of dataflow analysis over each program clause is proved to be independent of the size of the rest of the program.

UR - https://researchr.org/publication/sas%3A1993

M3 - Article in proceedings

SP - 27

EP - 44

BT - WSA'93

A2 - Cousot, Patrick

A2 - Falaschi, Moreno

A2 - Filé, Gilberto

A2 - Rauzy, Antoine

PB - Springer

T2 - 3rd International Workshop on Static Analysis

Y2 - 22 September 1993 through 24 September 1993

ER -