Using acceptors as transducers

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.