Search Constraints
You searched for:
Author
Chandra, Ashok K.
Remove constraint Author: Chandra, Ashok K.
Resource type
Book
Remove constraint Resource type: Book
Genre
technical reports
Remove constraint Genre: technical reports
1 - 3 of 3
Number of results to display per page
Search Results
- Title:
- On the power of programming features.
- Author:
- Chandra, Ashok K. and Manna, Zohar
- Author (no Collectors):
- Chandra, Ashok K. and Manna, Zohar
- Description:
- We consider the power of several programming features such as counters, pushdown stacks, queues, arrays, recursion and equality. In this study program schemas are used as the model for computation. The relations between the powers of these features is completely described by a comparison diagram.
- Topic:
- Computer science
- Subject:
- Stanford University. Computer Science Department
- Language:
- English
- Physical Description:
- 1 text file
- Publication Info:
- cau and Stanford (Calif.)
- Date:
- January 01, 1973
- Place created:
- Stanford (Calif.)
- Imprint:
- Stanford (Calif.), January 1, 1973
- Genre:
- technical reports
- Identifier:
- CS-TR-1973-333
- 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
- Title:
- Efficient compilation of linear recursive programs.
- Author:
- Chandra, Ashok K.
- Author (no Collectors):
- Chandra, Ashok K.
- Description:
- We consider the class of linear recursive programs. A linear recursive program is a set of procedures where each procedure can make at most one recursive call. The conventional stack implementation of recursion requires time and space both proportional to n, the depth of recursion. It is shown that in order to implement linear recursion so as to execute in time n one doesn't need space proportional to n: $n^\epsilon$ for arbitrarily small $\epsilon$ will do. It is also known that with constant space one can implement linear recursion in time $n^2$. We show that one can do much better: $n^{1+\epsilon}$ for arbitrarily small $\epsilon$. We also describe an algorithm that lies between these two: it takes time n.log(n) and space log(n). It is shown that several problems are closely related to the linear recursion problem, for example, the problem of reversing an input tape given a finite automaton with several one-way heads. By casting all these problems into a canonical form, efficient solutions are obtained simultaneously for all.
- Topic:
- Computer science
- Subject:
- Stanford University. Computer Science Department
- Language:
- English
- Physical Description:
- 1 text file
- Publication Info:
- cau and Stanford (Calif.)
- Date:
- April 01, 1972
- Place created:
- Stanford (Calif.)
- Imprint:
- Stanford (Calif.), April 1, 1972
- Genre:
- technical reports
- Identifier:
- CS-TR-1972-282
- 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
- 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
