Detecting determinate computations by bottom-up abstract interpretation

Roberto Giacobazzi; Laura Ricci

doi:10.1007/3-540-55253-7_10

Detecting determinate computations by bottom-up abstract interpretation

Roberto Giacobazzi
, Laura Ricci

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

One of the most interesting characteristics of logic programs is the ability of expressing nondeterminism in an elegant and concise way. On the other hand, implementation of nondeterminism poses serious problems both in the sequential and in the concurrent case. If determinate computations are detected through a static analysis, a noticeable reduction of the execution time may be obtained. This work describes a static analysis to detect determinate computations. The analysis does not require the knowledge of the activating modes of the predicate and it derives determinacies which may be inferred from the success set of the program.

Original language	English (US)
Title of host publication	ESOP 1992 - 4th European Symposium on Programming, Proceedings
Editors	Bernd Krieg-Bruckner
Publisher	Springer-Verlag
Pages	167-181
Number of pages	15
ISBN (Print)	9783540552536
DOIs	https://doi.org/10.1007/3-540-55253-7_10
State	Published - 1992
Externally published	Yes
Event	4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992 - Rennes, France Duration: Feb 26 1992 → Feb 28 1992

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	582 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992
Country/Territory	France
City	Rennes
Period	2/26/92 → 2/28/92

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-55253-7_10

Cite this

Giacobazzi, R., & Ricci, L. (1992). Detecting determinate computations by bottom-up abstract interpretation. In B. Krieg-Bruckner (Ed.), ESOP 1992 - 4th European Symposium on Programming, Proceedings (pp. 167-181). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 582 LNCS). Springer-Verlag. https://doi.org/10.1007/3-540-55253-7_10

Detecting determinate computations by bottom-up abstract interpretation. / Giacobazzi, Roberto; Ricci, Laura.
ESOP 1992 - 4th European Symposium on Programming, Proceedings. ed. / Bernd Krieg-Bruckner. Springer-Verlag, 1992. p. 167-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 582 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Giacobazzi, R & Ricci, L 1992, Detecting determinate computations by bottom-up abstract interpretation. in B Krieg-Bruckner (ed.), ESOP 1992 - 4th European Symposium on Programming, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 582 LNCS, Springer-Verlag, pp. 167-181, 4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992, Rennes, France, 2/26/92. https://doi.org/10.1007/3-540-55253-7_10

Giacobazzi R, Ricci L. Detecting determinate computations by bottom-up abstract interpretation. In Krieg-Bruckner B, editor, ESOP 1992 - 4th European Symposium on Programming, Proceedings. Springer-Verlag. 1992. p. 167-181. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-55253-7_10

Giacobazzi, Roberto ; Ricci, Laura. / Detecting determinate computations by bottom-up abstract interpretation. ESOP 1992 - 4th European Symposium on Programming, Proceedings. editor / Bernd Krieg-Bruckner. Springer-Verlag, 1992. pp. 167-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{04ca29730f964dc0a64854b6e9d48831,

title = "Detecting determinate computations by bottom-up abstract interpretation",

abstract = "One of the most interesting characteristics of logic programs is the ability of expressing nondeterminism in an elegant and concise way. On the other hand, implementation of nondeterminism poses serious problems both in the sequential and in the concurrent case. If determinate computations are detected through a static analysis, a noticeable reduction of the execution time may be obtained. This work describes a static analysis to detect determinate computations. The analysis does not require the knowledge of the activating modes of the predicate and it derives determinacies which may be inferred from the success set of the program.",

author = "Roberto Giacobazzi and Laura Ricci",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1992.; 4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992 ; Conference date: 26-02-1992 Through 28-02-1992",

year = "1992",

doi = "10.1007/3-540-55253-7\_10",

language = "English (US)",

isbn = "9783540552536",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer-Verlag",

pages = "167--181",

editor = "Bernd Krieg-Bruckner",

booktitle = "ESOP 1992 - 4th European Symposium on Programming, Proceedings",

}

TY - GEN

T1 - Detecting determinate computations by bottom-up abstract interpretation

AU - Giacobazzi, Roberto

AU - Ricci, Laura

PY - 1992

Y1 - 1992

N2 - One of the most interesting characteristics of logic programs is the ability of expressing nondeterminism in an elegant and concise way. On the other hand, implementation of nondeterminism poses serious problems both in the sequential and in the concurrent case. If determinate computations are detected through a static analysis, a noticeable reduction of the execution time may be obtained. This work describes a static analysis to detect determinate computations. The analysis does not require the knowledge of the activating modes of the predicate and it derives determinacies which may be inferred from the success set of the program.

AB - One of the most interesting characteristics of logic programs is the ability of expressing nondeterminism in an elegant and concise way. On the other hand, implementation of nondeterminism poses serious problems both in the sequential and in the concurrent case. If determinate computations are detected through a static analysis, a noticeable reduction of the execution time may be obtained. This work describes a static analysis to detect determinate computations. The analysis does not require the knowledge of the activating modes of the predicate and it derives determinacies which may be inferred from the success set of the program.

UR - https://www.scopus.com/pages/publications/84976753423

UR - https://www.scopus.com/pages/publications/84976753423#tab=citedBy

U2 - 10.1007/3-540-55253-7_10

DO - 10.1007/3-540-55253-7_10

M3 - Conference contribution

AN - SCOPUS:84976753423

SN - 9783540552536

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 167

EP - 181

BT - ESOP 1992 - 4th European Symposium on Programming, Proceedings

A2 - Krieg-Bruckner, Bernd

PB - Springer-Verlag

T2 - 4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992

Y2 - 26 February 1992 through 28 February 1992

ER -

Detecting determinate computations by bottom-up abstract interpretation

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this