Kurodas Problem
# Kurodas Problem

Kurodas Problem ist ein Begriff aus der Automatentheorie und Komplexitätstheorie.

Der Sprachwissenschaftler Sige-Yuki Kuroda hat sich mit der von Noam Chomsky definierten Hierarchie auseinandergesetzt und die kontextsensitiven Sprachen mit nichtdeterministischen linear beschränkten Automaten charakterisiert. Da er in seinen Bemühungen, das Verfahren deterministisch mit demselben Platz darzustellen, erfolglos war, formulierte er 1964 die berühmte Frage:

    Können die kontextsensitiven Sprachen von deterministischen linear beschränkten Automaten erkannt werden?

Eine weitere Frage, die er in derselben Arbeit formulierte, betraf den Komplementabschluss der kontextsensitiven Sprachen. Dieser wurde von Róbert Szelepcsényi und Neil Immerman unabhängig im Jahr 1987 allgemein für nichtdeterministische Platzkomplexität (mit gewissen kleinen technischen Einschränkungen) bewiesen (siehe auch Artikel zur Komplexitätsklasse NL).

