Determinacy and Subsumption of Single-Valued Bottom-Up Tree Transducers

• HASHIMOTO Kenji

  Graduate School of Information Science, Nagoya University

• SAWADA Ryuta

  Graduate School of Information Science and Technology, Osaka University

• ISHIHARA Yasunori

  Graduate School of Information Science and Technology, Osaka University

• SEKI Hiroyuki

  Graduate School of Information Science, Nagoya University

• FUJIWARA Toru

  Graduate School of Information Science and Technology, Osaka University

Abstract

This paper discusses the decidability of determinacy and subsumption of tree transducers. For two tree transducers T₁ and T₂, T₁ determines T₂ if the output of T₂ can be identified by the output of T₁, that is, there is a partial function f such that [[T₂]]=f∘[[T₁]] where [[T₁]] and [[T₂]] are tree transformation relations induced by T₁ and T₂, respectively. Also, T₁ subsumes T₂ if T₁ determines T₂ and the partial function f such that [[T₂]]=f∘[[T₁]] can be defined by a transducer in a designated class that T₂ 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 T₃ such that [[T₂]]=[[T₃]]∘[[T₁]] can be constructed if T₁ subsumes T₂.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E99.D (3), 575-587, 2016

  The Institute of Electronics, Information and Communication Engineers

Keywords

• determinacy
• subsumption
• tree transducer

Details

• CRID: 1390282679354138496
• NII Article ID: 130005131811
• DOI: 10.1587/transinf.2015fcp0015
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E99.D/3/E99.D_2015FCP0015/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed