Assignment Commands with Array References

Peter J. Downey, Ravi Sethi

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


Stratght line programs with assignment statements involving both simple and array variables are considered Two such programs are equivalent if they compute the same values as a function of the inputs. Testing the equivalence of array programs ts shown to be NP-hard If array variables are updated but never subsequently referenced, equivalence can be tested in polynomial time Programs without array varmbles can be tested for equivalence in expected linear time.

Original languageEnglish (US)
Pages (from-to)652-666
Number of pages15
JournalJournal of the ACM (JACM)
Issue number4
StatePublished - Oct 1 1978


  • NP-complete
  • array asstgnments
  • data structures
  • semanttcs

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'Assignment Commands with Array References'. Together they form a unique fingerprint.

Cite this