Assignment Commands and Array Structures

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.

Authors

• Peter J. Downey
• Ravi Sethi

Keywords

• Computational modeling
• Programmable logic arrays
• Software testing
• Software algorithms
• System testing
• Computer science
• Polynomials
• Interactive systems
• Debugging
• Input variables
• Efficient Algorithm
• Flow Control
• Test For Equality
• Linear Time
• Hash Function
• Array Elements
• Design Philosophy
• Axiomatic Approach
• Conditional Branches
• Subtree
• Simple Observation
• Node Update