Characterizing the Valuedness of Two-Way Finite Transducers

摘要

A transducer is infinite-valued if the maximal number of different outputs for an input string is not bounded by any constant. For one-way finite transducers, Weber gave sufficient and necessary conditions in terms of the structure of a transducer to characterize whether the transducer is infinite-valued or not. As crossing sequences in two-way automata often play similar roles as states in their one-way counterparts, we derive in this paper analogous criteria in the setting of crossing sequences to characterize the infinite-valuedness of two-way finite transducers.