For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2016/03/01
Online ISSN: 1745-1361
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---Developments of the Theory of Algorithms and Computation---)
determinacy, subsumption, tree transducer,
Full Text: PDF(558.8KB)>>
This paper discusses the decidability of determinacy and subsumption of tree transducers. For two tree transducers T1 and T2, T1 determines T2 if the output of T2 can be identified by the output of T1, that is, there is a partial function f such that [[T2]]=f∘[[T1]] where [[T1]] and [[T2]] are tree transformation relations induced by T1 and T2, respectively. Also, T1 subsumes T2 if T1 determines T2 and the partial function f such that [[T2]]=f∘[[T1]] can be defined by a transducer in a designated class that T2 belongs to. In this paper, we show that determinacy is in coNEXPTIME 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 T3 such that [[T2]]=[[T3]]∘[[T1]] can be constructed if T1 subsumes T2.