On the Valuedness of Symbolic Finite Transducers
Journal
Proceedings - 2020 International Computer Symposium, ICS 2020
Pages
120-125
Date Issued
2020
Author(s)
Yen D.-D
Abstract
Symbolic finite transducers are extensions of classical finite transducers. A transition of a symbolic finite transducer represents a (possibly infinite) set of transitions of a classical one. This setting allows symbolic finite transducers to succinctly recognize transductions. A transducer is k-valued if the maximal number of different outputs for an input string is bounded by k and it is finite-valued if it is k-valued for some k. In this paper, we study the valuedness problem for symbolic finite transducers. We show that for symbolic finite transducers over decidable labels, the k-valuedness problem is decidable. For finite transducers, Weber introduced two criteria to characterize infinite-valuedness, both of which can be easily transformed into properties for symbolic finite transducers. Although these two criteria are sufficient conditions for infinite-valuedness, they are not necessary conditions however. As a result, a third criterion is introduced in order to completely characterize the infinite-valuedness of symbolic finite transducers. ? 2020 IEEE.
Subjects
Computability and decidability; Finite transducers; Input string; Transducers
Type
conference paper