@misc{oai:tokyo-metro-u.repo.nii.ac.jp:00002124,
 author = {オガワ, コウスケ and Ogawa, Kousuke and 小川, 孝典},
 month = {Mar},
 note = {計算複雑さの理論の一分野として, AND-OR 木の研究がある.
我々は, randomized complexity を達成する乱択アルゴリズムを最適乱択アルゴ
リズムとよび, i-セット(i 2 f0; 1g) に対してコスト期待値が一定の乱択アルゴリズ
ムをEi-乱択アルゴリズムと定義する. 本論文では, 連結閉集合上の乱択アルゴリズ
ムについて, i-セットに対して最適であることとEi であることが同値であることを
証明する. これは, 鈴木-中村[SuNa] の結果の双対的な結果とみなすことができる.
また, 真理値割り当てからなる集合にグラフの構造を入れ、木の高さに関する構造
定理を示す.
付録として, 無限組み合わせ論におけるdiamond principle に関連したhitting
principle についての考察を加える. hitting principle をP   へ持ち上げ, P   に
おけるdiamond principle との関連づけを与える., 首都大学東京, 2013-03-25, 修士（理学）},
 title = {完全二分AND-OR 木に対する最適乱択アルゴリズムの特徴づけと木転置グラフの構造について},
 year = {2013}
}