imported>Harry8: typo

2017-09-13T14:55:50Z

typo

Neue Seite

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

Der Sprachwissenschaftler [[Sige-Yuki Kuroda]] hat sich mit der von [[Noam Chomsky]] definierten [[Chomsky-Hierarchie|Hierarchie]] auseinandergesetzt und die [[kontextsensitive Sprache|kontextsensitiven Sprachen]] mit [[Linear beschränkte Turingmaschine|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 [[NL (Komplexitätsklasse)|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.

[[Kategorie:Automatentheorie]]
[[Kategorie:Komplexitätstheorie]]

Kurodas Problem - Versionsgeschichte

imported>Harry8: typo