= Logspace composition by recomputation
{title2=$f,g\in\mathrm{FL}\Longrightarrow g\circ f\in\mathrm{FL}$}
To simulate $g$ on the virtual <input> $f(x)$, store the simulated <input>-head position and rerun the <logspace transducer> for $f$ whenever an <input> symbol is requested. Count emitted symbols until the requested position is reached. The intermediate output has <polynomial> length, so its positions take $O(\log n)$ <bits>, and the work space of $g$ is also $O(\log n)$. Storage used by successive recomputations is reused. This proves closure of <logspace-computable functions> under composition and transitivity of <logspace many-one reductions>.
Back to article page
