Open Questions from Hopcroft and Ullman

On page 281 of the 1979 edition the classic theory text of Hopcroft and Ullman lies two tables describing closure and decidability properties of various formal languages. Four entries in the table are labelled by "?" meaning the answer was not known. Those entries are

1. Are context-sensitive languages closed under complementation?
2. If L is context-sensitive is MIN(L) context sensitive? MIN(L) is the set of strings in L who do not have proper prefixes in L.
3. Is it decidable whether the complement of a given context-sensitive language is context-sensitive?
4. Is it decidable whether two given deterministic context-free languages are equal?

We now know the answers to all of these question are "Yes."

1. In 1988, Neil Immerman and Róbert Szelepcsényi independently showed that nondeterministic space is closed under complement. Since CSLs are equivalent to nondeterministic linear space we have that CSLs are also closed under complement. Immerman and Szelepcsényi received the 1995 Gödel Prize for this result. We will cover Immerman-Szelepcsényi in the next Foundations lesson.
2. By using Immerman-Szelepcsényi, one can create a nondeterministic linear time algorithm to check that x is in L and that all proper prefixes of x are not in L.
3. Trivially true by Immerman-Szelepcsényi.
4. This was the hard one. Only in 1997 did Géraud Sénizergues succeed in showing that the problem is decidable. For this work he received the 2002 Gödel Prize. Here is the simplified version of his result, a mere 58 pages.