木から文字列への決定性降下型変換器の早期化

• Item type: Trans(1)
• 公開日: 2019-05-21
• タイトル: 木から文字列への決定性降下型変換器の早期化
• タイトル / 言語: en
• タイトル: Earliest form on Deterministic Top-down Tree-to-string Transducers
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [発表概要，Unrefereed Presentation Abstract]
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 電気通信大学大学院情報理工学研究科情報・ネットワーク工学専攻
• 著者所属: 東北大学電気通信研究所
• 著者所属(英): en
• 著者所属(英): Graduate School of Informatics and Engineering, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Research Institute of Electrical Communication, Tohoku University
• 著者名: 高橋, 祐多; 中野, 圭介
• 著者名(英): Yuta, Takahashi; Keisuke, Nakano
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 木から文字列への決定性降下型変換器（deterministic top-down tree-to-string transducers，yDTs）は，木構造データを入力とし，文字列を出力するような関数を扱うモデルの1つである．与えられた2つのyDTが，あらゆる同じ入力に対して同じ出力をするかという等価性判定は，決定可能であることが知られている．既存の等価性判定アルゴリズムは，2つの半アルゴリズムを組み合わせることで等価性判定を行っているため，計算量の見積りが不可能である．一方，yDTが線型の場合，正規形を求めることでたかだか指数時間で決定できることが知られている．そのアルゴリズムでは，言語の最大共通接頭辞・接尾辞や周期性を利用することで早期化を行った後，最小化することで正規形を求め，等価性判定を行っている．そこで，計算量を見積もることができるyDTの等価性判定アルゴリズムの実現に向け，本発表では線型yDTの等価性判定アルゴリズムにおいて用いられる早期化を非線型yDTに対して適用できるよう一般化する．具体的には，yDTに対して正規先読みを追加することで，早期に出力可能な文字列を可能な限り早く出力する正規先読み付きyDTを構築する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A deterministic top-down tree-to-string transducer (yDT) is a model of functions which transform tree-structured data to a string. It is known that the equivalence problem on yDTs is decidable, that is, we can effectively check if given two yDTs output the same string for every input. Since the existing algorithm for the equivalence problem consists of two semi-algorithms, it is impossible to estimate its computational complexity. In the case where given yDTs are linear, the equivalence can be decided in at most exponential time to the size of yDT through their ‘normal forms’ which is obtained by constructing earliest yDT and minimizing the size of it. This approach relies on properties of the longest common prefix/suffix and the periodicity of language, which has never been discussed for general yDTs. In this presentation, we study earliest yDTs as the first step of another algorithm of which computational complexity can be determined. We introduce regular-lookahead to yDTs for generalizing the construction of earliest linear yDT. It makes it possible that the rule of yDT yields string as possible as earlier.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 12, 号 2, p. 13-13, 発行日 2019-05-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会