BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-71-250
       ENTRY:: November 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Program schemas with equality
        TYPE:: Technical Report
      AUTHOR:: Chandra, Ashok K.
      AUTHOR:: Manna, Zohar
        DATE:: December 1971
       PAGES:: 14
    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
               investigators.

               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.
       NOTES:: [Adminitrivia V1/Prg/19951101]
         END:: STAN//CS-TR-71-250