The search functionality is under construction.

Author Search Result

[Author] Ryuta SAWADA(1hit)

1-1hit
  • Determinacy and Subsumption of Single-Valued Bottom-Up Tree Transducers

    Kenji HASHIMOTO  Ryuta SAWADA  Yasunori ISHIHARA  Hiroyuki SEKI  Toru FUJIWARA  

     
    PAPER

      Pubricized:
    2015/12/16
      Vol:
    E99-D No:3
      Page(s):
    575-587

    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.