L

Remarks

Example: the language of balanced strings of brackets over $\set{(, )}$ lies in $\mathrm{L}$. A machine scans the input once and keeps the current depth in a binary counter, rejecting if the depth becomes negative. It accepts if the depth is $0$ at the end, and the counter needs $O(\log n)$ cells.

Non-example: a machine that first copies its input to a work tape uses $n$ cells. That machine does not show membership in L, since $n$ is not $O(\log n)$.

A machine in logarithmic space has only polynomially many configurations on inputs of length $n$. So it halts within polynomially many steps, and $\mathrm{L} \subseteq$ P. Omer Reingold proved that connectivity in undirected graphs lies in $\mathrm{L}$.