Contact Us

The History of Artificial Intelligence

Program schemas with equality.

purl.stanford.edu/hw921xt9932
Title:
Program schemas with equality.
Author:
Chandra, Ashok K.
Author (no Collectors):
Chandra, Ashok K.
Description:
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.
Topic:
Computer science
Subject:
Stanford University. Computer Science Department
Language:
English
Physical Description:
1 text file
Publication Info:
cau and Stanford (Calif.)
Date:
December 01, 1971
Place created:
Stanford (Calif.)
Imprint:
Stanford (Calif.), December 1, 1971
Genre:
technical reports
Identifier:
CS-TR-1971-250
Repository:
Stanford University. Libraries. Department of Special Collections and University Archives
Collection:
Stanford University, Department of Computer Science, Technical Reports and Stanford Artificial Intelligence Laboratory records, 1963-2009
Manuscript number:
3840/2