文献

J-GLOBAL ID：202002213851590563   整理番号：20A0854123

木評価問題のための読み込み分岐プログラム【JST・京大機械翻訳】

Read-Once Branching Programs for Tree Evaluation Problems

著者 (2件)： Iwama Kazuo (RIMS, Kyoto University, Kitashirakawa-Oiwakecho, Sakyo-ku, Kyoto, Japan) ,  Nagao Atsuki (The University of Electro-Communications, Chofu, Tokyo, Japan)
資料名： ACM Transactions on Computation Theory  (ACM Transactions on Computation Theory)
巻： 11  号： 1  ページ： 1-12  発行年： 2018年 
JST資料番号： W5690A  ISSN： 1942-3454  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： LとPを分離する最終目標に向けて,Cook,McKenzie,Wehr,Braverman,およびSanthanamは木評価問題(TEP)を導入した。固定整数hとk>0に対して,FT_h(k)は,高さhの完全で根づいた二値木として与えられ,各根ノードは[k]~2から[k]までの関数に関連し,各葉ノードは[k]において数を持つ。内部ノードvの値を自然に定義した。すなわち,関数fとその2つの子供ノードの値がaとbであるならば,vの値はf(a,b)である。著者らのタスクは,ボトムアップ方式でこの関数評価を逐次実行することによって,根ノードの値を計算することである。この問題は明らかにPにおいてあり,もし著者らがFT~h(k)を解く任意の分岐プログラムが任意の非有界関数rに対して少なくともk~r(h)状態を必要とするならば,この問題はLではなく,従って著者らの目標を達成することを証明できる。BP(i,e)の構造に対するthriティと呼ばれる制約を導入し,その問題を解決するためのアルゴリズムに対して,任意のthriティBPがΩ(k~h)状態を必要とすることを証明した。本論文では,リッド1回分岐プログラムに対する類似の下限を証明し,これにより,thriティ制約の性質であるBPにより読み出されたノードの次数に対する制限の除去を可能にした。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *子供
準シソーラス用語： ボトムアップ ,  有界 , 【Automatic Indexing@JST】

著者キーワード (5件)： 木評価問題 ,  分岐プログラム ,  下界 ,  読み込み分岐プログラム ,  空間複雑性

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 木 ,  評価 ,  問題 ,  読み込み ,  分岐