Correct computation rules for recursive languages

Peter J. Downey; Ravi Sethi

doi:10.1109/SFCS.1975.10

Correct computation rules for recursive languages

Peter J. Downey, Ravi Sethi

Computer Science

Research output: Contribution to journal › Conference article › peer-review

1 Scopus citations

Abstract

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 language	English (US)
Article number	4567857
Pages (from-to)	48-56
Number of pages	9
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume	1975-October
DOIs	https://doi.org/10.1109/SFCS.1975.10
State	Published - 1975
Event	16th Annual Symposium on Foundations of Computer Science, SFCS 1975 - Berkeley, United States Duration: Oct 13 1975 → Oct 15 1975

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1109/SFCS.1975.10

Cite this

@article{444c398ca5974ffa99fc3e68b88069c5,

title = "Correct computation rules for recursive languages",

abstract = "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.",

author = "Downey, {Peter J.} and Ravi Sethi",

note = "Publisher Copyright: {\textcopyright} 1975 IEEE.; 16th Annual Symposium on Foundations of Computer Science, SFCS 1975 ; Conference date: 13-10-1975 Through 15-10-1975",

year = "1975",

doi = "10.1109/SFCS.1975.10",

language = "English (US)",

volume = "1975-October",

pages = "48--56",

journal = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

issn = "0272-5428",

}

TY - JOUR

T1 - Correct computation rules for recursive languages

AU - Downey, Peter J.

AU - Sethi, Ravi

PY - 1975

Y1 - 1975

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85035009322&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85035009322&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1975.10

DO - 10.1109/SFCS.1975.10

M3 - Conference article

AN - SCOPUS:85035009322

SN - 0272-5428

VL - 1975-October

SP - 48

EP - 56

JO - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

JF - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

M1 - 4567857

T2 - 16th Annual Symposium on Foundations of Computer Science, SFCS 1975

Y2 - 13 October 1975 through 15 October 1975

ER -

Correct computation rules for recursive languages

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this