A.M. TURING AWARD WINNERS BY...

Richard ("Dick") Edwin Stearns DL Author Profile link

United States – 1993
Short Annotated Bibliography

Books

  1. Hartmanis, J. and Stearns, R.E., Algebraic Structure Theory of Sequential Machines, Prentice-Hall, 1966.
  2. Lewis, P.M., Rosenkrantz, D.J. and Stearns, R.E., Compiler Design Theory, Addison Wesley Publishing Co., 1976.
  3. Aumann, Robert J. and Maschler, Michael B. with the collaboration of Stearns, Richard E., Repeated Games with Incomplete Information, MIT Press, 1995. This book won the 1995 Lanchester Prize for the best contribution of the year to Operations Research

Selected Publications

  1. Hartmanis, J. and Stearns, R.E., “On the Computational Complexity of Algorithms,” Transactions of the American Mathematical Society, Vol. 117, Num. 5, May 1965, pp. 285-306. This is the paper that earned Hartmanis and Stearns the Turing Award.
  2. Stearns, R.E., J. Hartmanis and P.M. Lewis,Hierarchies of Memory Limited Computations,” Proceedings of the 6th Annual Symposium On Switching Circuit Theory & Logical Design, Oct. 1965. This paper extended computational complexity to space bounded classes. By separating work tape and input tape, sub-linear space classes were defined.
  3. Lewis, P.M. and R.E. Stearns, “Syntax-Directed Transduction,” Journal of the ACM, Vol. 15, July 1968, pp. 465-488, available here.This paper defined LL(k) grammars and showed how they could be exploited for certain syntax-directed translations.
  4. Stearns, R.E., “Convergent Transfer Schemes for N-Person Games,” Transactions of the American Mathematical Society, Vol. 134, December 1968, pp. 449-459. This paper showed that points in certain solution sets can be reached through a sequence of natural transfers rather than by computing the entire solution set.
  5. Rosenkrantz, D.J. and , R.E. Stearns, “Properties of Deterministic Top-Down Grammars,” Information and Control, Vol. 17, Num. 3, Oct. 1970, pp. 226-256. In this paper the LL(k) grammars were examined more closely, their properties explored, and an equivalence test described.
  6. Rosenkrantz, D.J., R.E. Stearns and P.M. Lewis, “An Analysis of Several Heuristics for the Traveling Salesman Problem,” SIAM Journal on Computing, Vol. 6, September 1977, pp. 563-581.  Heuristics are examined and analyzed for closeness to optimal solutions. Some of the analysis is also reported in the book “Computers and Intractability: A Guide to the Theory of NP-Completeness” by M. R. Gary and D. S Johnson.
  7. Rosenkrantz, D.J., R.E. Stearns and P.M. Lewis, “Consistency and Serializability in Concurrent Database Systems,” SIAM Journal on Computing, Vol. 13, August 1984, pp. 508-530.  This paper shows that (with the exception of certain read-only transactions) serializability is both necessary and sufficient for consistency.
  8. Stearns, R.E. and H.B. Hunt III, “Power Indices and Easier NP-complete Problems,” Mathematical Systems Theory, Vol. 23, 1990, pp. 209-225. This paper investigates how size complexity of reductions affects the conclusions one can make about hardness. It suggests “power index” as a way of refining the NP-completeness concept and speculates about the power index of several NP-complete problems.
  9. Stearns, Richard Edwin, “It's Time to Reconsider Time,” Communications of the ACM, Vol. 37, November 1994, pp. 95-99. Available hereThis is his Turing Award Lecture.
  10. Stearns, R.E. and , H.B. Hunt III, “An Algebraic Model for Combinatorial Problems,” SIAM Journal on Computing, Vol. 25, April 1996, pp. 448-476. This paper studies sum-of-product problems over commutative semi-rings and the applicability of these problems to combinatorial problems. The concept of a “structure tree” is offered as a useful way to display the structure of sums-of-products.
  11. Stearns, R.E. and H.B. Hunt III, “Exploiting Structure in Quantified Formulas,” Journal of Algorithms, Vol. 43, 2002, pp. 220-263. In this paper the “structure tree” concept is generalized to describe the structure of quantified formulas.
  12. Stearns, R.E. and H.B. Hunt III, “Resource Bounds and Subproblem Independence,” Theory of Computing Systems, Vol. 38, 2005, pp. 731-761. In this paper sub-linear space bounded computations are linked to sub-problem independence as displayed in a structure tree.