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.
Automata, Languages and Programming: Fifth Colloquium, Udine, Italy, July 17–21, 1978, 1978, p. 227-240
Main Research Area:
Lecture Notes in Computer Science
5th Colloquium on Automata, Languages and Programming, 1978