The Complexity of Equivalence and Containment for Free Single Variable Program Schemes
Fortune, Steven; Hopcroft, John E.; Schmidt, Erik Meineche
Non-containment for free single variable program schemes is shown to be NP-complete. A polynomial time algorithm for deciding equivalence of two free schemes, provided one of them has the predicates appearing in the same order in all executions, is given. However, the ordering of a free scheme is shown to lead to an exponential increase in size.
computer science; technical report
Previously Published As