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   Vol.E99-D   No.3   pp.575-587
Publication Date: 2016/03/01
Publicized: 2015/12/16
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2015FCP0015
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)>>
Buy this Article

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.