Accession Number:

ADA058448

Title:

The Complexity of Equivalence and Containment for Free Single Variable Program Schemes.

Descriptive Note:

Technical rept.,

Corporate Author:

CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Report Date:

1977-05-01

Pagination or Media Count:

28.0

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. Author

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE