Determinacy and Subsumption of Single-Valued Bottom-Up Tree Transducers
Kenji HASHIMOTO, Ryuta Sawada, Yasunori Ishihara, Hiroyuki Seki, Toru Fujiwara · IEICE Transactions on Information and Systems · 2016
This paper discusses the decidability of determinacy and subsumption of tree transducers.For two tree transducers T 1 and T 2 , T 1 determines T 2 if the output of T 2 can be identified by the output of T 1 , that is, there is a partial function f such that [[T 2 ]] = f • [[T 1 ]] where [[T 1 ]] and [[T 2 ]] are tree transformation relations induced by T 1 and T 2 , respectively.Also, T 1 subsumes T 2 if T 1 determines T 2 and the partial function f such that [[T 2 ]] = f • [[T 1 ]] can be defined by a transducer in a designated class that T 2 belongs to.In this paper, we show that determinacy is in coNEX-PTIME for single-valued linear extended bottom-up tree transducers as the determiner class and single-valued bottom-up tree transducers as the determinee class.We also show that subsumption is in coNEXPITME for these classes, and a bottom-up tree transducer T 3 such that [[T 2 ]] = [[T 3 ]] • [[T 1 ]] can be constructed if T 1 subsumes T 2 .