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

- Are context-sensitive languages closed under complementation?
- 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.
- Is it decidable whether the complement of a given
context-sensitive language is context-sensitive?
- Is it decidable whether two give deterministic context-free
languages are equal?

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

- 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.
- 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.
- Trivially true by
Immerman-Szelepcsényi.
- 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.

--

Posted by Lance Fortnow to My Computational Complexity Web Log at 5/28/2003 2:57:33 PMPowered by Blogger Pro