Search For:

Displaying 1-12 out of 12 total
Computational complexity of recursive sequnces
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By J. Hartmanis, R. E. Stearns
Issue Date:November 1964
pp. 82-90
In this paper we investigate how numbers, functions, and sequences can be classified according to their computational complexity. The computational complexity is measured by how fast the number or function can be computed by a multitape computer (Turing ma...
 
Property grammars and table machines
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By R. E. Stearns, P. M. Lewis
Issue Date:October 1968
pp. 106-119
The purpose of this paper is to generalize the methods of automata theory to accommodate infinite input alphabets and to propose a method of describing computer languages such as ALGOL-60 with more reliance on grammatical methods and less reliance on seman...
 
Syntax directed transduction
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By P. M. Lewis, R. E. Stearns
Issue Date:October 1966
pp. 21-35
A transduction is a mapping from one set of sequences to another. A syntax directed transduction is a particular type of transduction which is defined on the grammar of a context free language and which is meant to be a model of part of the translation pro...
 
Table machine simulation
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By R. E. Stearns, D. J. Rosenkrantz
Issue Date:October 1969
pp. 118-128
A pushdown table machine can be simulated by a computer in time n log log n where n is the number of table machine operations. A finite state table machine can be simulated in linear time.
 
Concurrency control for database systems
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By R. E. Stearns, P. M. Lewis, D. J. Rosenkrantz
Issue Date:October 1976
pp. 19-32
No summary available.
 
On the application of pair algebra to automata theory
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By R. E. Stearns, J. Hartmanis
Issue Date:November 1964
pp. 192-196
In this paper, we define and discuss generalizations of partition pairs on sequential machines. The object of these generalizations is to suggest a unified approach to problems of information flow and machine structure.
 
Approximate algorithms for the traveling salesperson problem
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By D. J. Rosenkrantz, R. E. Stearns, P. M. Lewis
Issue Date:October 1974
pp. 33-42
Several polynomial time algorithms finding
 
Hierarchies of memory limited computations
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By R. E. Stearns, J. Hartmanis, P. M. Lewis
Issue Date:October 1965
pp. 179-190
This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A
 
Memory bounds for recognition of context-free and context-sensitive languages
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By P. M. Lewis, R. E. Stearns, J. Hartmanis
Issue Date:October 1965
pp. 191-202
This paper investigates the computational complexity of binary sequences as measured by the rapidity of their generation by multitape Turing machines. A
 
Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)
Found in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing (STOC '94)
By H. B. Hunt, M. V. Marathe, R. E. Stearns, V. Radhakrishnan
Issue Date:May 1994
pp. 468-477
We present efficient new randomized and deterministic methods for transforming optimal solutions for a type of relaxed integer linear program into provably good solutions for the corresponding NP-hard discrete optimization problem. Without any constraint v...
     
Attributed translations(Extended Abstract)
Found in: Proceedings of the fifth annual ACM symposium on Theory of computing (STOC '73)
By D. J. Rosenkrantz, P. M. Lewis, R. E. Stearns
Issue Date:April 1973
pp. 160-171
Attributed translations are a means of specifying the input-output relation of a language processing device, such as for example the lexical or syntax box of a compiler. Considered as a mathematical object, an attributed translation is a mapping of certain...
     
Properties of deterministic top down grammars
Found in: Proceedings of the first annual ACM symposium on Theory of computing (STOC '69)
By D. J. Rosenkrantz, R. E. Stearns
Issue Date:May 1969
pp. 165-180
The class of context free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. These grammars, called LL(k) grammars where k is the amount of look-ahead are first defined and a procedure is g...
     
 1