https://scholars.lib.ntu.edu.tw/handle/123456789/580865
標題: | On the Valuedness of Symbolic Finite Transducers | 作者: | Yen D.-D HSU-CHUN YEN |
關鍵字: | Computability and decidability; Finite transducers; Input string; Transducers | 公開日期: | 2020 | 起(迄)頁: | 120-125 | 來源出版物: | Proceedings - 2020 International Computer Symposium, ICS 2020 | 摘要: | 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. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85102206960&doi=10.1109%2fICS51289.2020.00033&partnerID=40&md5=64c12419d7f6bbb555bb26e6a3a77035 https://scholars.lib.ntu.edu.tw/handle/123456789/580865 |
DOI: | 10.1109/ICS51289.2020.00033 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。