Kurodas Problem

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 kontextsensiven 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).

Literatur

• Róbert Szelepcsényi: The Method of Forced Enumeration for Nondeterministic Automata. In: Acta Informatica 26, 1988, ISSN 0001-5903, S. 279–284.
• Neil Immerman: Nondeterministic Space is Closed Under Complementations. In SIAM Journal on Computing 17, 1988, ISSN 0097-5397, S. 935–938.
• S.-Y. Kuroda: Classes of Languages and Linear-Bounded Automata. In: Information and Control 7, 1964, ISSN 0019-9958, S. 207–223.