We wish to use a given nondeterministic two-way multi-tape acceptor as a tr
ansducer by supplying the contents for only some of its input tapes, and as
king it to generate the missing contents for the other tapes. We provide he
re an algorithm for assuring beforehand that this transduction always resul
ts in a finite set of answers. We also develop an algorithm for evaluating
these answers whenever the previous algorithm indicated their finiteness. F
urthermore, our algorithms can be used for speeding up the simulation of th
ese acceptors even when not used as transducers. (C) 2001 Elsevier Science
B.V. All rights reserved.