Skip to main content


eCommons@Cornell

eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/6845
Title: The Complexity of Equivalence and Containment for Free Single Variable Program Schemes
Authors: Fortune, Steven
Hopcroft, John E.
Schmidt, Erik Meineche
Keywords: computer science
technical report
Issue Date: May-1977
Publisher: Cornell University
Citation: http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR77-310
Abstract: 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.
URI: http://hdl.handle.net/1813/6845
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
77-310.pdf1.04 MBAdobe PDFView/Open
77-310.ps584.62 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us