Editing Context-sensitive language (section)

== Computational properties ==

Computationally, a context-sensitive language is equivalent to a linear bounded [[nondeterministic Turing machine]], also called a [[linear bounded automaton]]. That is a non-deterministic Turing machine with a tape of only <math>kn</math> cells, where <math>n</math> is the size of the input and <math>k</math> is a constant associated with the machine. This means that every formal language that can be decided by such a machine is a context-sensitive language, and every context-sensitive language can be decided by such a machine.

This set of languages is also known as NLINSPACE or NSPACE(''O''(''n'')), because they can be accepted using linear space on a non-deterministic Turing machine.<ref>{{citation
 | last = Rothe | first = Jörg
 | isbn = 978-3-540-22147-0
 | location = Berlin
 | mr = 2164257
 | page = 77
 | publisher = Springer-Verlag
 | series = Texts in Theoretical Computer Science. An EATCS Series
 | title = Complexity theory and cryptology
 | year = 2005}}.</ref>  The class LINSPACE (or DSPACE(''O''(''n''))) is defined the same, except using a [[Deterministic automaton|deterministic]] Turing machine.  Clearly LINSPACE is a subset of NLINSPACE, but it is not known whether LINSPACE&thinsp;=&thinsp;NLINSPACE.<ref>{{citation
 | last = Odifreddi | first = P. G.
 | isbn = 978-0-444-50205-6
 | location = Amsterdam
 | mr = 1718169
 | page = 236
 | publisher = North-Holland Publishing Co.
 | series = Studies in Logic and the Foundations of Mathematics
 | title = Classical recursion theory. Vol. II
 | volume = 143
 | year = 1999}}.</ref>