Program schemas with equality
Abstract/Contents
- 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.
Description
Type of resource | text |
---|---|
Form | technical reports |
Extent | 1 text file |
Place | Stanford (Calif.) |
Date created | December 1, 1971 |
Language | English |
Digital origin | reformatted digital |
Creators/Contributors
Author | Chandra, Ashok K. |
---|
Subjects
Subject | Stanford University. Computer Science Department |
---|---|
Subject | Computer science |
Genre | Technical reports |
Bibliographic information
Finding Aid | |
---|---|
Technical Report # | CS-TR-1971-250 |
Location | https://purl.stanford.edu/hw921xt9932 |
Location | 3840/2 |
Repository | Stanford University. Libraries. Department of Special Collections and University Archives |
Access conditions
- Use and reproduction
- The materials are open for research use and may be used freely for non-commercial purposes with an attribution. For commercial permission requests, please contact the Stanford University Archives (universityarchives@stanford.edu).
Collection
Stanford University, Department of Computer Science, Technical Reports
View other items in this collection in SearchWorksStanford Artificial Intelligence Laboratory records, 1963-2009
View other items in this collection in SearchWorksAlso listed in
Loading usage metrics...