Yen D.-DHSU-CHUN YEN2023-06-092023-06-0920228905401https://www.scopus.com/inward/record.uri?eid=2-s2.0-85124467115&doi=10.1016%2fj.ic.2022.104870&partnerID=40&md5=60992d3583a4f697c9864e7740188e10https://scholars.lib.ntu.edu.tw/handle/123456789/632494A 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, sufficient and necessary conditions exist in terms of the structure of a transducer to characterize whether the transducer is infinite-valued or not, yielding the decidability result of the finite-valuedness problem. As crossing sequences in two-way automata often play similar roles as states in their one-way counterparts, we consider analogous criteria in the setting of crossing sequences to characterize the infinite-valuedness of two-way finite transducers. The characterization leads to a decidability proof for the valuedness problem of two-way finite transducers. © 2022 Elsevier Inc.Crossing sequence; Finite transducer; ValuednessTransducers; Crossing sequence; Finite transducers; Input string; Sufficient and necessary condition; Two ways; Two-way automata; Valuedness; Computability and decidabilityjournal article10.1016/j.ic.2022.1048702-s2.0-85124467115