Kurodas Problem

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

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

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.

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.