Der Sprachwissenschaftler S.-Y. 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 kontextsensiven 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, pp 279--284, 1988
• Neil Immerman: Nondeterministic Space is Closed Under Complementations. In SIAM Journal on Computing 17, pp 935--938, 1988.
• S.-Y. Kuroda: Classes of Languages and Linear-Bounded Automata. In Information and Control 7, pp 207--223, 1964.

Automatentheorie | Komplexitätstheorie | Formale Sprachen