Correct computation rules for recursive languages

Peter J. Downey, Ravi Sethi

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


This paper considers simple LISP-like languages for the recursive definition of functions, focusing upon the connections between formal computation rules for calculation and the mathematical semantics of recursive definitions. A computation rule is correct when it is capable of computing the minimal fixpoint of a recursive definition. We give necessary and sufficient conditions for the correctness of rules under (a) all possible interpretations and (b) particular interpretations.

Original languageEnglish (US)
Article number4567857
Pages (from-to)48-56
Number of pages9
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 1975
Event16th Annual Symposium on Foundations of Computer Science, SFCS 1975 - Berkeley, United States
Duration: Oct 13 1975Oct 15 1975

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Correct computation rules for recursive languages'. Together they form a unique fingerprint.

Cite this