Assignment commands and array structures

Peter J. Downey; Ravi Sethi

doi:10.1109/SFCS.1976.4567887

Assignment commands and array structures

Peter J. Downey, Ravi Sethi

Computer Science

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

2 Scopus citations

Abstract

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.

Original language	English (US)
Article number	4567887
Pages (from-to)	57-66
Number of pages	10
Journal	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume	1976-October
DOIs	https://doi.org/10.1109/SFCS.1976.4567887
State	Published - 1976
Event	17th Annual Symposium on Foundations of Computer Science, SFCS 1976 - Houston, United States Duration: Oct 25 1976 → Oct 27 1976

ASJC Scopus subject areas

General Computer Science

Access to Document

10.1109/SFCS.1976.4567887

Cite this

@article{dc53cfb52f0e4953b6d09876c59b5e85,

title = "Assignment commands and array structures",

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

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

note = "Publisher Copyright: {\textcopyright} 1976 Institute of Electrical and Electronics Engineers, Inc.; 17th Annual Symposium on Foundations of Computer Science, SFCS 1976 ; Conference date: 25-10-1976 Through 27-10-1976",

year = "1976",

doi = "10.1109/SFCS.1976.4567887",

language = "English (US)",

volume = "1976-October",

pages = "57--66",

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

issn = "0272-5428",

}

TY - JOUR

T1 - Assignment commands and array structures

AU - Downey, Peter J.

AU - Sethi, Ravi

PY - 1976

Y1 - 1976

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

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

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

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

U2 - 10.1109/SFCS.1976.4567887

DO - 10.1109/SFCS.1976.4567887

M3 - Conference article

AN - SCOPUS:84976827426

SN - 0272-5428

VL - 1976-October

SP - 57

EP - 66

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

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

M1 - 4567887

T2 - 17th Annual Symposium on Foundations of Computer Science, SFCS 1976

Y2 - 25 October 1976 through 27 October 1976

ER -

Assignment commands and array structures

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this