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

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)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1977
Accession Number
ADA058448

Entities

People

  • Erik Meineche Schmidt
  • John Hopcroft
  • Steven Fortune

Organizations

  • Department of Computer Science, Cornell University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computational Complexity
  • Computer Science
  • Computers
  • Graph Theory
  • Information Science
  • Language
  • New York
  • Polynomials
  • Trees (Data Structures)
  • Universities

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Mathematical Modeling and Probability Theory.