ログイン 新規登録
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

  1. 論文誌(トランザクション)
  2. プログラミング(PRO)
  3. Vol.12
  4. No.2

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

https://ipsj.ixsq.nii.ac.jp/records/195823
https://ipsj.ixsq.nii.ac.jp/records/195823
842c7d84-148f-45bb-b3fa-4471cda46dad
名前 / ファイル ライセンス アクション
IPSJ-TPRO1202009.pdf IPSJ-TPRO1202009.pdf (100.6 kB)
Copyright (c) 2019 by the Information Processing Society of Japan
オープンアクセス
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
著者名 高橋, 祐多

× 高橋, 祐多

高橋, 祐多

Search repository
中野, 圭介

× 中野, 圭介

中野, 圭介

Search repository
著者名(英) Yuta, Takahashi

× Yuta, Takahashi

en Yuta, Takahashi

Search repository
Keisuke, Nakano

× Keisuke, Nakano

en Keisuke, Nakano

Search repository
論文抄録
内容記述タイプ 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
収録物識別子 AA11464814
書誌情報 情報処理学会論文誌プログラミング(PRO)

巻 12, 号 2, p. 13-13, 発行日 2019-05-21
ISSN
収録物識別子タイプ ISSN
収録物識別子 1882-7802
出版者
言語 ja
出版者 情報処理学会
戻る
0
views
See details
Views

Versions

Ver.1 2025-01-19 22:55:01.321876
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3