DSPACE

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "DSPACE" – news · newspapers · books · scholar · JSTOR (October 2009) (Learn how and when to remove this message)

In

• REG = DSPACE(O(1)), where REG is the class of regular languages. In fact, REG = DSPACE(o(log log n)) (that is, Ω(log log n) space is required to recognize any non-regular language).^[1][2]

Proof: Suppose that there exists a non-regular language L ∈ DSPACE(s(n)), for s(n) = o(log log n). Let M be a Turing machine deciding L in space s(n). By our assumption L ∉ DSPACE(O(1)); thus, for any arbitrary ${\displaystyle k\in \mathbb {N} }$, there exists an input of M requiring more space than k.

Let x be an input of smallest size, denoted by n, that requires more space than k, and ${\displaystyle {\mathcal {C}}}$ be the set of all configurations of M on input x. Because M ∈ DSPACE(s(n)), then ${\displaystyle |{\mathcal {C}}|\leq 2^{c.s(n)}=o(\log n)}$, where c is a constant depending on M.

Let S denote the set of all possible crossing sequences of M on x. Note that the length of a crossing sequence of M on x is at most ${\displaystyle |{\mathcal {C}}|}$: if it is longer than that, then some configuration will repeat, and M will go into an infinite loop. There are also at most ${\displaystyle |{\mathcal {C}}|}$ possibilities for every element of a crossing sequence, so the number of different crossing sequences of M on x is

${\displaystyle |S|\leq |{\mathcal {C}}|^{|{\mathcal {C}}|}\leq (2^{c.s(n)})^{2^{c.s(n)}}=2^{c.s(n).2^{c.s(n)}}<2^{2^{2c.s(n)}}=2^{2^{o(\log \log n)}}=o(n)}$

According to pigeonhole principle, there exist indexes i < j such that ${\displaystyle {\mathcal {C}}_{i}(x)={\mathcal {C}}_{j}(x)}$, where ${\displaystyle {\mathcal {C}}_{i}(x)}$ and ${\displaystyle {\mathcal {C}}_{j}(x)}$ are the crossing sequences at boundary i and j, respectively.

Let x' be the string obtained from x by removing all cells from i + 1 to j. The machine M still behaves exactly the same way on input x' as on input x, so it needs the same space to compute x' as to compute x. However, |x' | < |x|, contradicting the definition of x. Hence, there does not exist such a language L as assumed. □

The above theorem implies the necessity of the

• L = DSPACE(O(log n))
• PSPACE = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(n^{k})}$
• EXPSPACE = ${\displaystyle \bigcup _{k\in \mathbb {N} }{\mathsf {DSPACE}}(2^{n^{k}})}$

Machine models

DSPACE is traditionally measured on a

Since many symbols might be packed into one by taking a suitable power of the alphabet, for all c ≥ 1 and f such that f(n) ≥ 1, the class of languages recognizable in c f(n) space is the same as the class of languages recognizable in f(n) space. This justifies usage of big O notation in the definition.

Hierarchy theorem

The

${\displaystyle f:\mathbb {N} \to \mathbb {N} }$

${\displaystyle O(f(n))}$

${\displaystyle o(f(n))}$

Relation with other complexity classes

DSPACE is the deterministic counterpart of