@inproceedings{bd2048dba8c24f798b3043c949295ec5,
title = "Programming with equations: A framework for lazy parallel evaluation",
abstract = "Huet and Levy pioneered lazy sequential evaluation of equational programs based on the concepts of strong-sequentiality and needed redexes. Natural extensions of their strategy are not well-suited for parallel evaluation since they do not support independent searches for needed redexes along different paths in the input term. Furthermore, the size of compiled code can be exponential in program size. We therefore propose a different notion of sequentiality called path-sequentiality that overcomes these drawbacks and thus provides a natural framework for lazy parallel evaluation. We present a sound and complete algorithm for lazy parallel normalization of path-sequential systems. We show that our algorithm is optimal in the sense that its time complexity is bounded only by the time required to perform the needed reductions. The results presented in this paper are applicable to functional languages as well through the transformation of Laville.",
author = "Sekar, \{R. C.\} and Ramakrishnan, \{I. V.\}",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1994.; 11th International Conference on Automated Deduction, CADE, 1992 ; Conference date: 15-06-1992 Through 18-06-1992",
year = "1992",
doi = "10.1007/3-540-55602-8\_196",
language = "English",
isbn = "9783540556022",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "618--632",
editor = "Deepak Kapur",
booktitle = "Automated Deduction — CADE-11 - 11 th International Conference on Automated Deduction, Proceedings",
}