In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions.
A log space transducer,
M
O(logn)
M
f\colon\Sigma\ast → \Sigma\ast
\Sigma
M
w
f(w)
A language
A\subseteq\Sigma\ast
B\subseteq\Sigma\ast
f
A
B
w\inA\ifff(w)\inB
This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction:
Transitivity holds because it is possible to feed the output tape of one reducer (A→B) to another (B→C). At first glance, this seems incorrect because the A→C reducer needs to store the output tape from the A→B reducer onto the work tape in order to feed it into the B→C reducer, but this is not true. Each time the B→C reducer needs to access its input tape, the A→C reducer can re-run the A→B reducer, and so the output of the A→B reducer never needs to be stored entirely at once.