Author name cluster

Peter J. Downey

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

FOCS Conference 1976 Conference Paper

Assignment Commands and Array Structures

Peter J. Downey
Ravi Sethi

Straight line programs in which array elements can be referenced and set are considered. Two programs are equivalent if they compute the same expression as a function of the inputs. Testing the equivalence of programs with arrays is shown to be NP-complete, while programs without arrays can be tested for equivalence in linear time. Equivalence testing takes polynomial time when programs have either no references or no assignments to array elements.

Details

FOCS Conference 1975 Conference Paper

Correct Computation Rules for Recursive Languages (Extended Abstract)

Peter J. Downey
Ravi Sethi

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.

Details