Complexity Theory Markus Bläser, Balagopal Komarath

News

Róbert Szelepcsényi and Neil Immerman

Written: 08.11.2019 12:30 Written By: Balagopal Komarath

Róbert Szelepcsényi, The Method of Forced Enumeration for Nondeterministic Automata (1987)

 
As pointed out to me after the lecture, Róbert Szelepcsényi is a Slovak.
 
Both papers are in English and I assume they missed it because they were published close together. Also, both papers use the NTM definition to prove the theorem and reach the same conclusion.
 
An interesting corollary is that context-sensitive languages are closed under complementation.
 

Both of them were awarded the Gödel prize in 1995 for this work.



Privacy Policy | Legal Notice
If you encounter technical problems, please contact the administrators