Fortune, Steven2; Hopcroft, John2; Schmidt, Erik Meineche4
Giorgio Ausiello, Corrado Böhm
1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 unknown3 Department of Computer Science, Science and Technology, Aarhus University4 Department of Computer Science, Science and Technology, Aarhus University
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