Assignment Commands with Array References

Peter J. Downey; Ravi Sethi

doi:10.1145/322092.322104

Assignment Commands with Array References

Peter J. Downey
, Ravi Sethi

Computer Science

Research output: Contribution to journal › Article › peer-review

23 Scopus citations

Abstract

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 language	English (US)
Pages (from-to)	652-666
Number of pages	15
Journal	Journal of the ACM (JACM)
Volume	25
Issue number	4
DOIs	https://doi.org/10.1145/322092.322104
State	Published - Oct 1 1978

Keywords

NP-complete
array asstgnments
data structures
semanttcs

ASJC Scopus subject areas

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

Access to Document

10.1145/322092.322104

Cite this

@article{0b82ae88fbaa48879111fdf5988a0a9f,

title = "Assignment Commands with Array References",

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

keywords = "NP-complete, array asstgnments, data structures, semanttcs",

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

year = "1978",

month = oct,

day = "1",

doi = "10.1145/322092.322104",

language = "English (US)",

volume = "25",

pages = "652--666",

journal = "Journal of the ACM (JACM)",

issn = "0004-5411",

publisher = "Association for Computing Machinery (ACM)",

number = "4",

}

TY - JOUR

T1 - Assignment Commands with Array References

AU - Downey, Peter J.

AU - Sethi, Ravi

PY - 1978/10/1

Y1 - 1978/10/1

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

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

KW - NP-complete

KW - array asstgnments

KW - data structures

KW - semanttcs

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

UR - https://www.scopus.com/pages/publications/0018020102#tab=citedBy

U2 - 10.1145/322092.322104

DO - 10.1145/322092.322104

M3 - Article

AN - SCOPUS:0018020102

SN - 0004-5411

VL - 25

SP - 652

EP - 666

JO - Journal of the ACM (JACM)

JF - Journal of the ACM (JACM)

IS - 4

ER -

Assignment Commands with Array References

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this