Richard Stearns (1936-2026)

Richard Stearns (right) and Juris Hartmanis in May 1963. The main theorem from their seminal paper is on the blackboard. Stearns sent Lance this picture to help celebrate the 50th anniversary of their paper.

Richard Stearns died on August 29, 2026.  Readers of this blog probably know him from the Hartmanis-Stearns paper On the computational complexity of algorithms which appeared in Transactions of the American Mathematical Society in 1965, and his paper with F. C. Hennie that gave the still tightest known separation for the deterministic time hierarchy.

The Hartmanis-Stearns paper first defined DTIME(T(n)) and other classes and named our field and this blog.  That paper has been honored in two ways:

1) The paper was one of the reasons Hartmanis and Stearns won the Turing Award in 1993.

2) Lance Fortnow chose that paper as one of his favorites, see here.

--------

In this post we discuss a different great paper by Stearns. First some background.

Consider the following problems.

1) Find a function \(f\) such that:

If \(L\) is a regular language and has an NFA of size \(n\) then it has a DFA of size \(\le f(n).\)

(Size is number of states.)

That one we know: \(f(n)=2^n\) suffices.

2) Find a function \(f\) such that:

If \(L\) has a CFG of size \(n\) then it has a PDA of size \(\le f(n).\)

(We assume the CFG is in Chomsky Normal Form and size is the number of nonterminals.)

That one we know: \(f(n)=n+O(1)\) suffices.

3) Find a function \(f\) such that:

If \(L\) is a regular language and has a CFG of size \(n\) then it has a DFA of size \(\le f(n).\)

Meyer and Fischer showed that \(HALT \le_T f\). Beigel and Gasarch later improved this to \(INF \le_T f \) and showed that was tight.

-----------------

Is there any pair of devices such that the gap is greater than exponential but not undecidable?

Richard Stearns in the paper A regularity test for pushdown machines showed the following:

If L is a reg lang with a DPDA of size n then it has a DFA of size \( \le n^{n^{n^{O(n)}}}\)

The size of a DPDA is the number of states plus stack symbols.

Leslie Valiant in the paper Regularity and related problems for deterministic pushdown automata improved this to:

If L is a reg lang with a DPDA of size n then it has a DFA of size \( \le 2^{2^{O(n)}}\).

which matches a lower bound in the Meyer-Fischer paper. Both Stearns and Valiant's results are interesting since the blow up is greater than exponential but still computable.