Fortune, StevenHopcroft, John E.Schmidt, Erik Meineche2007-04-232007-04-231977-05http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR77-310https://hdl.handle.net/1813/6845Non-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.1068976 bytes598648 bytesapplication/pdfapplication/postscripten-UScomputer sciencetechnical reporttechnical report