Report Number: CS-TR-71-250
Institution: Stanford University, Department of Computer Science
Title: Program schemas with equality
Author: Chandra, Ashok K.
Author: Manna, Z ohar
Date: December 1971
Abstract: We discuss the class of program schemas augmented with
equality tests, that is, tests of equality between terms.
In the first part of the paper we discuss and illustrate the
"power" of equality tests. It turns out that the class of
program schemas with equality is more powerful than the
"maximal" classes of schemas suggested by other
In the second part of the paper we discuss the decision
problems of program schemas with equality. It is shown for
example that while the decision problems normally considered
for schemas (such as halting, divergence, equivalence,
isomorphism and freedom) are solvable for Ianov schemas, they
all become unsolvable if general equality tests are added. We
suggest, however, limited equality tests which can be added
to certain subclasses of program schemas while preserving
their solvable properties.