Assignment commands and array structures

Peter J. Downey, Ravi Sethi

Research output: Contribution to journalConference articlepeer-review

2 Scopus citations


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 languageEnglish (US)
Article number4567887
Pages (from-to)57-66
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
StatePublished - 1976
Event17th Annual Symposium on Foundations of Computer Science, SFCS 1976 - Houston, United States
Duration: Oct 25 1976Oct 27 1976

ASJC Scopus subject areas

  • Computer Science(all)


Dive into the research topics of 'Assignment commands and array structures'. Together they form a unique fingerprint.

Cite this