首页    期刊浏览 2024年12月06日 星期五
登录注册

文章基本信息

  • 标题:木から文字列への決定性トップダウン変換の等価性判定アルゴリズムの実用性について
  • 本地全文:下载
  • 作者:高橋 祐多 ; 中野 圭介
  • 期刊名称:コンピュータ ソフトウェア
  • 印刷版ISSN:0289-6540
  • 出版年度:2018
  • 卷号:35
  • 期号:4
  • 页码:52-71
  • DOI:10.11309/jssst.35.52
  • 出版社:Japan Society for Software Science and Technology
  • 摘要:

    一般に関数の等価性判定問題は決定不能であるが,関数の定義に構文的な制約を加えることで決定可能にすることができる. そのような制約の 1 つとして,木から文字列への決定性トップダウン変換(deterministic top-down tree-to-string transducer, y DT)が存在し, 等価性判定が決定可能な関数としては,比較的広い範囲のものを扱うことができる. この y DT の等価性判定の決定可能性は 2015 年に Seidl らによって示されたが,2 つの半アルゴリズムを組み合わせることによって証明されており, 計算量が特定できず,実用性が確認されていない. そこで,本論文では yDT の等価性判定を行うプログラムを実装し,Seidl らの等価性判定アルゴリズムが実用に堪えうるものか検証する.

国家哲学社会科学文献中心版权所有