Program Schemas with Equality
Abstract
The authors discuss the class of program schemas augmented with equality tests, that is, tests of equality between terms. In the first part of the paper the authors 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 the authors 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. The authors suggest, however, limited equality tests which can be added to certain subclasses of program schemas while preserving their solvable properties.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1971
- Accession Number
- AD0740127
Entities
People
- Ashok K. Chandra
- Zohar Manna
Organizations
- Stanford University