Kuroda's problem

from Wikipedia, the free encyclopedia

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.