. . "20525930"^^ . "In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, , has three tapes: \n* A read-only input tape. \n* A read/write work tape (bounded to at most symbols). \n* A write-only, write-once output tape. will be designed to compute a log-space computable function (where is the alphabet of both the input and output tapes). If is executed with on its input tape, when the machine halts, it will have remaining on its output tape."@en . . . "2625"^^ . . . . "Log-space transducer"@en . . . . . . . "In computational complexity theory, a log space transducer (LST) is a type of Turing machine used for log-space reductions. A log space transducer, , has three tapes: \n* A read-only input tape. \n* A read/write work tape (bounded to at most symbols). \n* A write-only, write-once output tape. will be designed to compute a log-space computable function (where is the alphabet of both the input and output tapes). If is executed with on its input tape, when the machine halts, it will have remaining on its output tape. A language is said to be log-space reducible to a language if there exists a log-space computable function that will convert an input from problem into an input to problem in such a way that . This seems like a rather convoluted idea, but it has two useful properties that are desirable for a reduction: 1. \n* The property of transitivity holds. (A reduces to B and B reduces to C implies A reduces to C). 2. \n* If A reduces to B, and B is in L, then we know A is in L. Transitivity holds because it is possible to feed the output tape of one reducer (A\u2192B) to another (B\u2192C). At first glance, this seems incorrect because the A\u2192C reducer needs to store the output tape from the A\u2192B reducer onto the work tape in order to feed it into the B\u2192C reducer, but this is not true. Each time the B\u2192C reducer needs to access its input tape, the A\u2192C reducer can re-run the A\u2192B reducer, and so the output of the A\u2192B reducer never needs to be stored entirely at once."@en . "1025777081"^^ . . . . . . . . . .