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