Kuroda's problem
Kuroda's problem is a term from automata theory and complexity theory .
The linguist Sige-Yuki Kuroda has dealt with the hierarchy defined by Noam Chomsky and characterized the context-sensitive languages with nondeterministic linearly limited automata . Since he was unsuccessful in his efforts to represent the procedure deterministically with the same place, he formulated the famous question in 1964 :
- Can the context-sensitive languages be recognized by deterministic linearly bounded automata?
Another question that he formulated in the same paper concerned the complement of the context-sensitive languages. This was proven independently by Róbert Szelepcsényi and Neil Immerman in 1987 for nondeterministic space complexity (with certain small technical restrictions) (see also article on complexity class NL ).
literature
- Róbert Szelepcsényi: The Method of Forced Enumeration for Nondeterministic Automata . In: Acta Informatica 26, 1988, ISSN 0001-5903 , pp. 279-284.
- Neil Immerman: Nondeterministic Space is Closed Under Complementations . In SIAM Journal on Computing 17, 1988, ISSN 0097-5397 , pp. 935-938.
- S.-Y. Kuroda: Classes of Languages and Linear-Bounded Automata . In: Information and Control 7, 1964, ISSN 0019-9958 , pp. 207-223.