武永 康彦
| 情報・ネットワーク工学専攻 | 准教授 |
| Ⅰ類（情報系） | 准教授 |
- プロフィール:
アルゴリズムと計算量の理論、論理関数の性質の研究に従事
研究者情報
研究活動情報
論文
- On the Power of Lookahead in Single-Player PuyoPuyo
Y.Takenaga; S.Kikuchi; H.Quan
ICGA Journal, 43巻, 2号, 掲載ページ 102-113, 出版日 2021年, 査読付
研究論文（学術雑誌）, 英語 - QUIXO is EXPTIME-complete
Shohei Mishiba; Yasuhiko Takenaga
Information Processing Letters, Elsevier, 162巻, 105995号, 出版日 2020年10月, 査読付
研究論文（学術雑誌）, 英語 - Matchstick Puzzles on a Grid
Y.Takenaga; S.Mishiba an; H.Sugiyama
Graphs and Combinatorics, Springer, 36巻, 2号, 掲載ページ 347-357, 出版日 2020年03月, 査読付
研究論文（学術雑誌）, 英語 - Anti-Slide Placements of Pentominoes
Y.Takenaga; X.Yang; A.Inada
The Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3) 2019, 掲載ページ 121-122, 出版日 2019年09月07日, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Matchstick Puzzles on a Grid
Yasuhiko Takenaga; Shohei Mishiba; Haruka Sugiyama
Proc. the 20th Japan Conference on Discrete and Computational Geometry, Graphs, and Games, 掲載ページ 137-138, 出版日 2017年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Strategies for Single-Player PuyoPuyo
Yasuhiko Takenaga; Yo Shimada
ICGA JOURNAL, 39巻, 2号, 掲載ページ 87-101, 出版日 2017年, 査読付
研究論文（学術雑誌）, 英語 - Number of Three-Point Tilings with Triangle Tiles
Yasuhiko Takenaga; Narutoshi Tanaka; Takahiro Habara
Journal of Information Processing, Information Processing Society of Japan, 23巻, 3号, 掲載ページ 305-309, 出版日 2015年, 査読付
研究論文（学術雑誌）, 英語 - Satogaeri, Hebi and Suraromu are NP-Complete
Shohei Kanehiro; Yasuhiko Takenaga
3RD INTERNATIONAL CONFERENCE ON APPLIED COMPUTING AND INFORMATION TECHNOLOGY (ACIT 2015) 2ND INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND INTELLIGENCE (CSI 2015), 掲載ページ 46-51, 出版日 2015年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Shikaku and Ripple Effect are NP-Complete
Y.Takenaga; S.Aoyagi; S.Iwata; T.Kasai
Congressus Numerantium, Utilitas Mathematica Publishing Inc., 216巻, 掲載ページ 119-127, 出版日 2013年12月, 査読付
研究論文（学術雑誌）, 英語 - NP-completeness of pandemic
Kenichiro Nakai; Yasuhiko Takenaga
Journal of Information Processing, 20巻, 3号, 掲載ページ 723-726, 出版日 2012年, 査読付
研究論文（学術雑誌）, 英語 - Precoloring Extension on Grid Graphs
Yasuhiko Takenaga
Proc. the China-Japan Joint Confernece on Computational Geometry, Graphs and Applications (CGGA 2010), 掲載ページ 102-103, 出版日 2010年10月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - STONEHENGE: OUTCOME OF ALL FIRST MOVES AND PSPACE-COMPLETENESS
Yasuhiko Takenaga; Hikari Mori; Shigeki Iwata
ICGA JOURNAL, 33巻, 1号, 掲載ページ 34-41, 出版日 2010年03月, 査読付
研究論文（学術雑誌）, 英語 - PSPACE-completeness of an escape problem
Yasuhiko Takenaga; Shigeru Arai
INFORMATION PROCESSING LETTERS, 108巻, 4号, 掲載ページ 229-233, 出版日 2008年10月, 査読付
研究論文（学術雑誌）, 英語 - Tree-shellability of restricted DNFs
Yasuhiko Takenaga; Nao Katougi
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E91D巻, 4号, 掲載ページ 996-1002, 出版日 2008年04月, 査読付
研究論文（学術雑誌）, 英語 - Vertex Coloring of Chordal+k_1e-k_2e Graphs
Y.Takenaga; Y.Miura
IWOCA2007, to appear巻, 出版日 2007年11月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - TETRAVEX is NP-complete
Yasuhiko Takenaga; Toby Walsh
INFORMATION PROCESSING LETTERS, 99巻, 5号, 掲載ページ 171-174, 出版日 2006年09月, 査読付
研究論文（学術雑誌）, 英語 - 組合せ最適化問題としてのぷよぷよの連鎖数判定問題
松金輝久; 武永康彦
電子情報通信学会論文誌D, 一般社団法人電子情報通信学会, J89-D巻, 3号, 掲載ページ 405-413, 出版日 2006年03月, 査読付
研究論文（学術雑誌）, 日本語 - Vertex coloring of comparability +ke and -ke graphs
Yasuhiko Takenaga; Kenichi Higashide
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 4271巻, 掲載ページ 102-+, 出版日 2006年
研究論文（国際会議プロシーディングス）, 英語 - Tree-shellability of Boolean functions
Y Takenaga; K Nakajima; S Yajima
THEORETICAL COMPUTER SCIENCE, 262巻, 1-2号, 掲載ページ 633-647, 出版日 2001年07月, 査読付
研究論文（学術雑誌）, 英語 - Recognition of ordered tree-shellable Boolean functions based on OBDDs
Y Takenaga
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E84D巻, 1号, 掲載ページ 28-33, 出版日 2001年01月, 査読付
研究論文（学術雑誌）, 英語 - Hardness of Identifying the Minimum Ordered Binary Decision Diagram(共著)
Y. Takenaga; S. Yajima
Discrete Applied Mathematics, 107巻, 1-3号, 掲載ページ 191-201, 出版日 2000年12月, 査読付
研究論文（学術雑誌）, 英語 - Size of ordered binary decision diagrams representing threshold functions(共著)
K.Hosaka; Y.Takenaga; T.Kaneda; S.Yajima
Theoretical Computer Science, 180巻, 1-2号, 掲載ページ 47-60, 出版日 1997年07月, 査読付
研究論文（学術雑誌）, 英語 - Computational Power of Nondeterministic Ordered Binary Decision Diagrams and Their Subclasses(共著)
K.Takagi; K.Nitta; H.Bouno; Y.Takenaga; S.Yajima
電子情報通信学会英文論文誌A, E80A巻, 4号, 掲載ページ 663-669, 出版日 1997年04月, 査読付
研究論文（学術雑誌）, 英語 - Size and Variable Ordering of OBDDs Representing Threshold Functions(共著)
Y.Takenaga; M.Nouzoe; S.Yajima
COCOON'97, 掲載ページ 91-100, 出版日 1997年, 査読付
研究論文（国際会議プロシーディングス）, 英語 - On the Size of Ordered Binary Decision Diagrams Representing Threshold Functions(共著)
K.Hosaka; Y.Takenaga; S.Yajima
ISAAC'94, 834巻, 掲載ページ 584-592, 出版日 1994年08月, 査読付
研究論文（国際会議プロシーディングス）, 英語 - On the Computational Power of Binary Decision Diagrams(共著)
H.Sawada; Y.Takenaga; S.Yajima
電子情報通信学会英文論文誌D, E77D巻, 6号, 掲載ページ 611-618, 出版日 1994年06月, 査読付
研究論文（学術雑誌）, 英語 - Computational Complexity of Manipulating Binary Decision Diagrams(共著)
Y.Takenaga; S.Yajima
電子情報通信学会英文論文誌D, E77D巻, 6号, 掲載ページ 642-647, 出版日 1994年06月, 査読付
研究論文（学術雑誌）, 英語 - 連想メモリによるメモリ型並列計算モデルの計算能力(共著)
武永康彦; 高木直史; 矢島脩三
情報処理学会論文誌, 一般社団法人情報処理学会, 33巻, 4号, 掲載ページ 415-422, 出版日 1992年04月, 査読付
研究論文（学術雑誌）, 日本語 - Computational Power of Memory-Based Parallel Computation Models with Communication(共著)
Y.Takenaga; S.Yajima
電子情報通信学会英文論文誌D, E75D巻, 1号, 掲載ページ 89-94, 出版日 1992年01月, 査読付
研究論文（学術雑誌）, 英語 - メモリ型並列計算モデルとその計算能力(共著)
高木直史; 武永康彦; 矢島脩三
情報処理学会論文誌, 31巻, 11号, 掲載ページ 1565-1571, 出版日 1990年11月, 査読付
研究論文（学術雑誌）, 日本語
講演・口頭発表等
- ヤバラスのPSPACE完全性
武藤里樹; 武永康彦
日本語, 情報処理学会第87回全国大会
発表日 2025年03月14日
開催期間 2025年03月13日- 2025年03月15日 - 色数1の一般化ぷよぷよの連鎖数判定問題
水越開理; 武永康彦
口頭発表（一般）, 日本語, 情報処理学会第87回全国大会
発表日 2025年03月14日
開催期間 2025年03月13日- 2025年03月15日 - 一人用ダイヤモンドゲームにおける最小手数について
豊永桂輔; 武永康彦
ポスター発表, 日本語, 2024年電子情報通信学会総合大会
発表日 2024年03月07日
開催期間 2024年03月04日- 2024年03月08日 - 様々なグラフ上での「うさぎと猟犬」の必勝性について
橋本悠希; 武永康彦
ポスター発表, 日本語, 2024年電子情報通信学会総合大会
発表日 2024年03月07日
開催期間 2024年03月04日- 2024年03月08日 - Approximate Block Diagonalization of Symmetric Matrices Using Quantum Annealing
Koushi Teramoto; Masaki Kugaya; Shuhei Kudo; Yasuhiko Takenaga; Yusaku Yamamoto
口頭発表（一般）, 英語, The International Conference on High Performance Computing in Asia-Pacific Region (HPC Asia 2024), 査読付
発表日 2024年01月16日
開催期間 2024年01月15日- 2024年01月17日 - 泥棒の速度が異なるCops and Robbersの格子上における戦略
小森良汰朗、武永康彦
ポスター発表, 日本語, 2023年電子情報通信学会総合大会
発表日 2023年03月07日
開催期間 2023年03月07日- 2023年03月10日 - Finding a Shortest Solution for Single-Player Chinese Checkers is NP-complete
Yuya Nakamura; Yasuhiko Takenaga
口頭発表（一般）, 英語, 2022年電子情報通信学会総合大会
発表日 2022年03月17日
開催期間 2022年03月15日- 2022年03月18日 - 三人一般化七並べの必勝性
田中天希; 武永康彦
ポスター発表, 日本語, 2022年電子情報通信学会総合大会
発表日 2022年03月15日
開催期間 2022年03月15日- 2022年03月18日 - ペントミノを用いたアンチスライドパズルの解の列挙
宇賀神慶行; 武永康彦
ポスター発表, 日本語, 2022年電子情報通信学会総合大会
発表日 2022年03月15日
開催期間 2022年03月15日- 2022年03月18日 - グラフ上のダイヤモンドゲームの計算複雑さ
山田貴之; 武永康彦
ポスター発表, 日本語, 2022年電子情報通信学会総合大会
発表日 2022年03月15日
開催期間 2022年03月15日- 2022年03月18日 - NP-completeness of peg solitaire on graphs
Kazushi Ito; Yasuhiko Takenaga
口頭発表（一般）, 英語, The 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games (TJCDCG3 2020+1), 査読付, 国際会議
発表日 2021年09月04日
開催期間 2021年09月03日- 2021年09月05日 - 二人一般化七並べの戦略
田中天希; 武永康彦
ポスター発表, 日本語, 電子情報通信学会2020年総合大会, 国内会議
発表日 2020年03月17日
開催期間 2020年03月17日- 2020年03月20日 - グラフ上のペグソリティアの計算困難性
伊藤和司; 武永康彦
ポスター発表, 日本語, 電子情報通信学会2020年総合大会, 国内会議
発表日 2020年03月17日
開催期間 2020年03月17日- 2020年03月20日 - 先読みを考慮した一人ぷよぷよの必勝性
菊地翔; 武永康彦
口頭発表（一般）, 日本語, 第82回情報処理学会全国大会, 国内会議
発表日 2020年03月05日 - Anti-Slide Placements of Pentominoes
Yasuhiko Takenaga; Xi Yang; Asuka Inada
口頭発表（一般）, 英語, The 22nd Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2019), 国際会議
発表日 2019年09月07日 - 幅３色数３の一人ぷよぷよの必勝性
菊地翔; 武永康彦
ポスター発表, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2019年03月19日 - 格子上での Cops and Robbers の方向のみ認知可能なルール
大久保辰哉; 武永康彦
ポスター発表, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2019年03月19日 - ペントミノを用いたアンチスライドパズルの解の列挙
楊璽; 武永康彦; 稲田明透河
口頭発表（一般）, 日本語, 第８１回情報処理学会全国大会, 国内会議
発表日 2019年03月15日 - On Winning Strategies for Tetris Type Games
Yasuhiko Takenaga; Masaki Katsuno; Hushan Quan
口頭発表（一般）, 英語, The 20th Korea-Japan Joint Workshop on Algorithms and Computation, Seoul, Korea, 国際会議
発表日 2017年08月25日 - 先読みありの1人ぷよぷよの必勝性
全虎山; 武永康彦
ポスター発表, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2017年03月22日 - 一般化QUIXOの計算複雑さ
三柴翔平; 武永康彦
ポスター発表, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2017年03月22日 - 一人用落ち物パズルゲームの必勝性
勝野誠基; 武永康彦
ポスター発表, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2017年03月22日 - グラフ上の一般化ペグソリティア
山本和明; 武永康彦
ポスター発表, 日本語, 電子情報通信学会総合大会, 国内会議
発表日 2017年03月22日 - 格子上のマッチ棒パズル
三柴翔平; 武永康彦; 杉山晴香
口頭発表（一般）, 日本語, 組合せゲーム・パズルプロジェクト第12回研究集会, 国内会議
発表日 2017年03月06日 - 木+keグラフの部分グラフ同型判定アルゴリズム
上野 豊; 武永康彦
ポスター発表, 日本語, 電子情報通信学会2014年総合大会
発表日 2014年03月19日 - フロンティア法を用いた根無し木の列挙
吉田隆史; 武永康彦
ポスター発表, 日本語, 電子情報通信学会2014年総合大会, 国内会議
発表日 2014年03月19日 - 色数と盤面の幅を限定したぷよぷよの必勝性
島田陽; 武永康彦
口頭発表（一般）, 日本語, 組合せゲーム・パズル第9回ミニ研究集会
発表日 2014年02月28日 - 比較可能-keグラフの頂点彩色問題のパラメータ化計算量（共著）
斎藤惇; 武永康彦
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 2012年03月 - パラメータ化permutationグラフの頂点彩色問題
小寺諒; 武永康彦
口頭発表（一般）, 日本語, 2012年電子情報通信学会総合大会
発表日 2012年03月 - 木+keグラフの同型性判定問題
上野豊; 武永康彦
口頭発表（一般）, 日本語, 2012年電子情報通信学会総合大会
発表日 2012年03月 - パラメータ化グラフに対するFixed-Parameterアルゴリズムの設計手法
岩永耕平; 武永康彦
口頭発表（一般）, 日本語, 2010年電子情報通信学会総合大会
発表日 2010年03月 - ナンバーリンクのＮＰ完全性と問題の列挙
古妻浩一; 武永康彦
口頭発表（一般）, 日本語, 電子情報通信学会,コンピュテーション研究会
発表日 2010年03月 - 多変量閾値関数の非明示的OBDD表現
中山昌光; 武永康彦
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告,コンピュテーション研究会
発表日 2008年03月 - OBDDを用いた画像処理アルゴリズム
番能孝生; 武永康彦
口頭発表（一般）, 日本語, 2008年電子情報通信学会総合大会
発表日 2008年03月 - Chordal+k_1e-k_2eグラフの頂点彩色問題
三浦勇介; 武永康彦
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告,コンピュテーション研究会
発表日 2007年03月 - 種々の制限を加えたTree-Shellable論理関数判定問題の計算複雑さ
加藤木直; 武永康彦; 石橋尚
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告,コンピュテーション研究会
発表日 2006年03月 - Coloring Comparability-ke Graphs
Y. Takenaga
口頭発表（一般）, 英語, LAシンポジウム
発表日 2006年02月 - リテラルの出現回数に制限を加えたTree-Shellable論理関数の判定複雑さ
加藤木直; 武永康彦
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 2005年05月 - 区間グラフのOBDD表現について
松川弘明; 武永康彦
口頭発表（一般）, 日本語, 2005年電子情報通信学会総合大会,2005年電子情報通信学会総合大会
発表日 2005年03月 - ブロック化分岐プログラムにおける変数順序と表現能力の関係
小関一弘; 武永康彦
口頭発表（一般）, 日本語, 情報処理学会研究報告
発表日 2004年03月 - 変数の出現回数が制限されたBranching Programの表現能力(共著)
河村亨; 武永康彦
口頭発表（一般）, 日本語, LAシンポジウム
発表日 2002年01月 - Complexity of Recognizing Tree-Shellable Functions
Y.Takenaga
口頭発表（一般）, 日本語, 電子情報通信学会技術報告
発表日 2001年11月 - Recognition of Tree-Shellable Boolean Functions
Y. Takenaga
口頭発表（一般）, 英語, LAシンポジウム
発表日 2001年07月 - Tree-Shellable論理関数の判定の複雑さ(共著)
門野伸史; 武永康彦
口頭発表（一般）, 日本語, LAシンポジウム
発表日 2001年01月 - 幅に制限を加えたOBDDの等価性判定(共著)
市村昌一; 武永康彦
口頭発表（一般）, 日本語, 電子情報通信学会技術研究報告
発表日 2000年11月 - Checking ordered tree-shellability of boolean function based on OBDDs
Y. Takenaga
口頭発表（一般）, 英語, 電子情報通信学会技術研究報告
発表日 1999年10月
共同研究・競争的資金等の研究課題
- パラメータや盤面を変更したゲームの必勝戦略と計算複雑さ
武永康彦
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 研究代表者, 23K11380
研究期間 2023年04月 - 2027年03月 - 組合せ的前処理と量子アニーリングの融合による行列計算の加速手法
山本 有作; 武永 康彦
日本学術振興会, 科学研究費助成事業 挑戦的研究(萌芽), 電気通信大学, 挑戦的研究(萌芽), 研究分担者, 22K19772
研究期間 2022年06月 - 2025年03月 - グラフ上のゲームおよびオンライン性を持つゲームの必勝性
武永 康彦
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 研究代表者, オンライン性を持つゲームの必勝性に関しては、主に落ちものゲームの一種であるぷよぷよを１人ゲームとして扱い、盤面の幅と色数を変更した場合に関する従来研究を、入力ピースの先読みが可能な場合に拡張した。主な結果として、どれだけ先読みが多くても色数が多ければプレイヤーの必敗となることを、盤面の幅が２および３の場合に対して証明した。 グラフ上のゲームについては、グラフ上のペグソリティアやチャイニーズチェッカー（ダイヤモンドゲーム）等のペグ移動ゲームを扱い、これらに関する可解性の判定や必勝性判定などの問題の計算困難性を証明した。また、これらのゲームのルールの変種における必勝性についても扱った。, 18K11601
研究期間 2018年04月 - 2022年03月 - ゲーム・パズルにおけるオンライン問題と計算複雑さ
武永 康彦
日本学術振興会, 科学研究費助成事業 基盤研究(Ｃ), 電気通信大学, 基盤研究(Ｃ), 研究代表者, オンライン性を持つ落ち物パズルゲームであるぷよぷよを1人ゲームとして扱い、その必勝性について研究を行った。必勝とは、プレーヤが一定の高さ以上にピースを積み上げることなく、永久にプレイできることをいう。実際のゲームと同様の入力の先読みがある場合とない場合について、ピースの色数と盤面の幅、先読みのできる入力の個数をパラメータとして、プレーヤが必勝あるいは必敗となる十分条件等を明らかにした。また、その証明手法が他の類似のパズルゲームに応用できることを示した。 また、格子上のマッチ棒パズル、対戦型ゲームであるQUIXOについて、その必勝性判定のアルゴリズム、計算複雑さを示した。, 15K00505
研究期間 2015年10月 - 2018年03月 - ゲーム情報学：Ａｎｄ－Ｏｒ木の探索とゲーム・パズルの難しさの研究
岩田 茂樹; 武永 康彦; 笠井 琢美; 伊藤 大雄
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 本研究は、ゲーム情報学全般にわたる研究のうち、(1) And-Or 木のコンピュータによる探索、と (2) ゲームやパズルの複雑さに関する研究を行う、ことを目的とする。 And-Or 木（ゲーム木）のコンピュータによる探索では通常、評価関数が用いられる。ゲーム木の自然なモデルを定め、ゲーム木のある深さにおいて深さ優先探索により探索する局面数を考える。完全な評価関数に確率 p(0 - パラメータ化グラフアルゴリズムの研究
武永 康彦
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 比較可能グラフから辺の削除を行って得られる比較可能-keグラフをはじめ、置換グラフ、グリッドグラフに辺の削除や追加を行って得られるグラフ族などに対する頂点彩色問題、木に辺を追加したグラフの同型性判定問題に対する効率的なアルゴリズムの設計、計算困難性の証明を行った。また、効率的なアルゴリズムが設計可能となる、問題とパラメータ化グラフ族の性質の組合せを明らかにした。, 21500007
研究期間 2009年 - 2011年 - 論理関数表現のモデルとシンボリックアルゴリズム
武永 康彦; 湊 真一
日本学術振興会, 科学研究費助成事業 特定領域研究, 電気通信大学, 特定領域研究, 1.二分決定グラフによるデータ表現については、第一に、二分決定グラフの構造を論理関数で表現する二分決定グラフの非明示的表現を用いて、効率的な表現が可能な論理関数について研究を行ない、多変量閾値関数を入力変数のビット長に依存しないサイズで表現できることを示した。 第二に、A07班山下との共同研究により、量子論理関数を効率よく表現するためのOBDDの変種データ構造を比較検討し、山下が以前に提案したDecisionDiagrams for Matrix Functions(DDMFs)の有効性を理論的に考察した。このデータ構造が、量子論理回路に特有の制約条件をうまく利用しており、単純なOBDDよりも一層データを圧縮し、処理効率を高めていることを明らかにした。 2.OBDDに基づくシンボリックアルゴリズムについては、前年度に引き続き、トポロジカルソートの列挙、OBDDによる画像処理アルゴリズムについて研究を行なった。前者では先行頂点数等を求めることにより従来法より計算過程でのOBDDサイズを大幅に抑えられることを示した。後者ではOBDD予測符号化を用いることによりOBDDサイズが圧縮可能であり、提案済みの画像処理アルゴリズムをほぼそのまま利用できることを示した。また、OBDDを用いたナンバーリンクの解法、問題の正当性の判定手法の提案・実装を行なった。, 16092207
研究期間 2004年 - 2007年 - 形式言語理論の自然言語処理への応用
笠井 琢美; 蓮沼 徹; 武永 康彦; 岩田 茂樹
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 本科学研究費補助金による研究の目的は、形式言語理論、学習理論、計算量理論などの計算機科学の基礎理論で得られたいろいろな結果を自然言語処理に応用しようとするものである。得られた成果は次のようにまとめることができる。形式言語理論で研究されてきた文法モデルに、文脈自由木文法というものがある。この文法は、文字列言語としては、インデックス言語と呼ばれる言語のクラスを定義する。しかし、このクラスは多項式時間では処理できないという結果が知られている。我々は、この文脈自由木文法に自然な制限を加え、Spine Grammarと呼ぶ新しい文法を定義した。この文法のクラスは、TAG(Tree Adjoining Grammar)と同じ文字列言語のクラスを定義し、TAGより自然な木言語のクラスを生成する。この結果はTheory of Computing Systems 33に掲載された。また、学習理論として、順序機械が極限同定可能であることを証明した。順序機械は、最も基本的な言語変換機モデルである。この結果は電子情報通信学会論文誌に掲載された。導入したSpine Grammarは生成モデルであり、直接言語処理アルゴリズムには適用することが難しい。そこで、この文法モデルに対応する解析モデルを構成した。このモデルを転送スタック付プッシュダウン・オートマトンと呼ぶ。この結果は電子情報通信学会論文誌に掲載された。研究分担者の岩田は、アルゴリズムの下界を求める研究でいくつかの成果を出した。(Inform.and Comput.に掲載)武永は、ブール関数のOBDD計算量に関し、いくつかの結果を得た。(Discrete Applied Math.とTheoret.Comp.Sci.に掲載)また、蓮沼はグラフアルゴリズムに関するいくつかの結果を得た。(Discrete Applied Math.とJournal of AlgerithmsとInform. Processing Lett.に掲載), 10680341
研究期間 1998年 - 2001年 - 計算機科学における下界の研究
岩田 茂樹; 蓮沼 徹; 武永 康彦; 笠井 琢美
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 本科学研究費補助金により得られた成果は、次のようにまとめられる。 (m, n)-マージングネットワークにおける最小比較器数M(m, n)を求める問題を考える。M(n, n), n【less than or equal】5,n=7,8,9の値が既知であり、M(6,6)に対しては16【less than or equal】M(6,6)【less than or equal】17が知られていた。研究代表者等はM(6,6)=17を証明した。(論文掲載済) また、M(m, n)に関する下界定理を導いた。Batcherのodd-even mergeにおける(m, n)-マージングネットワークの比較器数をC(m, n)とすると、M(4,n)=C(4,n),n≡0,1,3mod 4,M(5,n)=C(5,n)、n≡0,1,5mod 8であることを示し、Batcherの(6,8k+6)-,(7,8k+7)-,(8,8k+8)-マージングネットワークが最適であることを証明した。またこの下界定理によりYao and Yaoの未解決問題を25年ぶりに解くことができた。(論文掲載済) 盤の一辺の大きさをnに拡張した将棋盤の上での詰将棋を考え、この一般化詰将棋問題が指数時間完全であることを示した。(論文掲載済) n頂点の有向非閉路グラフGの各頂点に1,2,…,nの整数を割り当て、Gの有向辺(u, v)に対し、頂点uに割り当たる整数がvに割り当たる整数より小さい1,2,…,nの順列の個数をT(G)と定める。この定義によればT(G)をO(n^2・n!)ステップで計算できるが、T(G)をO(n^2・2^n)で計算する新しいアルゴリズムを考案した。(論文は研究会で発表済) 研究分担者の笠井は、推論アルゴリズムや形式言語に関する成果をあげた。武永は、順序付2分決定図やTree-shallable関数の性質を明らかにした。蓮沼は、グラフ理論の性質やグラフアルゴリズムを提案した。これらはいずれも本研究をすすめるための基礎研究であり、今後の研究に活かす予定である。, 10680342
研究期間 1998年 - 2001年 - 論理関数のグラフ表現の性質と双対比への応用
武永 康彦
日本学術振興会, 科学研究費助成事業 奨励研究(A), 電気通信大学, 奨励研究(A), 本研究では、二分決定木や分岐プログラムなど理論上実際上重要な、グラフによる論理関数の表現法について、研究を行なってきた。本年度の研究成果の詳細は以下の通りである。 1. 分岐プログラムの性質と表現能力に関する研究 分岐プログラムの一種で、効率的な論理関数の表現法として知られる二分決定グラフについて、論理関数の正の例および負の例からの学習可能性について研究を行なった。具体的には、すべての例を満たす最小サイズの二分決定グラフを求める問題が、関数をしきい値関数に制限した場合でもNP困難であることを示した。 2. 論理関数双対化等への応用 前年度に提案した、論理関数を二分木表現の1つの経路が1つの素項に対応するような正論理関数のクラスについて、決定木の変数順序を固定した場合(ordered tree-shellable関数)、固定しない場合(tree-shellable関数)にわけて、さらに研究を進めた。 (Ordered)tree-shellableであることがわかれば、効率良い双対化等、その特長の活用が可能だが、それにはこれらのクラスに属するかどうかの判定が必要となる。Quadratic関数(積和形表現の各積項のリテラル数が2個)に対しては多項式時間で判定可能であるが、一般の場合についても、リテラル数が2個の積項だけを取り出した関数が(ordered)tree-shellableであることが、必要条件となることを示した。また、前年度のプログラムを改良し、変数の置換によって等価となる関数を1個とみなした場合も含め、6変数までの関数に対して、これらの性質を持つ関数の個数を具体的に求めた。, 09780267
研究期間 1997年 - 1998年 - マイクロプロセッサの形式的論理設計検証システムの試作研究
矢島 脩三; 荻野 博幸; 武永 康彦; 浜口 清治; 平石 裕実
日本学術振興会, 科学研究費助成事業 基盤研究(A), 京都大学, 基盤研究(A), 本研究では、大規模な順序回路設計の中でも、特にマイクロプロセッサの正しさを厳密に保証するための形式的検証システムの試作を目指している。算術演算回路はマイクロプロセッサの重要な構成要素のひとつであるが、特に乗算器などの算術演算回路を検証することは一般に難しかった。これに対して、本研究では二分モーメントグラフによる新しいアルゴリズムを開発・実装して、従来手法では扱いきれなかった乗算器の検証が、現実的な時間で検証可能であることを世界で初めて示した。また、より直観的な記述が可能な時相論理である線形時間型の論理LTL (Linear Time Temporal Logic)に対して、従来より効率的な検証アルゴリズムを構築・実装して、有効性を示した。一方、マイクロプロセッサのような回路の設計検証を、論理回路レベルで直接行うことは、あまり現実的とはいえない。そこで本研究では、データパスなどを抽象化するために、限量子のない等号付き第一階述語論理を取り上げて、上記の線形時間型の時相論理に類似した時相演算子を導入し、時間に関する性質の直観的な記述が容易な体系を構築した。この論理について、まず、設計検証に用いる恒真判定問題が決定可能であることを証明した。次にこのアルゴリズムを時間および領域量の点から改良して実装し、その有効性を示した。また、設計検証において基盤技術となっている二分決定グラフについて、その変数順序付け問題がNP完全であることや、OR節点と呼ばれる特殊な節点を導入した場合の、二分決定グラフの表現能力について研究を行った。, 07558155
研究期間 1995年 - 1996年 - 論理関数高速処理機構に関する基礎的研究
矢島 修三; 安岡 孝一; 荻野 博幸; 武永 康彦; 濱口 清治; 高木 直史
日本学術振興会, 科学研究費助成事業 一般研究(B), 京都大学, 一般研究(B), 本研究では、共有二分決定グラフを中心に、論理関数処理の高速化に関して理論と応用の両面から基礎的研究をおこなった。 1.論理関数処理のアルゴリズム・計算複雑さに関する研究 二分決定グラフによる基本的な論理関数処理である、論理演算、既約化の並列アルゴリズムを示し、その計算複雑さを明らかにした。また、二分決定グラフによる論理関数の表現能力について、多項式サイズの二分決定グラフで表現できる論理関数のグラフと他のクラスの関係を明らかにした。さらに、しきい値関数を表現する二分決定グラフのサイズについて研究をおこなった。 2.論理関数処理機構に関する研究 二次記憶を用い、従来手法とは異なる幅優先の処理手法を適用することにより、主記憶上に記憶できない非常に大規模な共有二分決定グラフを高速に処理する手法を開発し、実験により評価をおこなった。また、メモリの高集積化技術の発展にともない非常に高い並列性を実現できる可能性を持つ、内容アドレスメモリ(CAM)上で共有二分決定グラフ処理をおこなうための手法を提案した。 3.論理関数処理に基づく設計支援に関する研究 論理関数処理の論理設計支援への応用として、スキャン付き順序回路に対する短いテスト系列の生成手法、および、非同期式順序回路の種々の状態割り当てについて、その解を得る手法を提案した。また、論理設計支援以外の分野への応用として、ブール処理を用いて種々の組合せ問題を解くアルゴリズムを提案した。, 05452352
研究期間 1993年 - 1994年 - 時相理論に基づく論理設計の形式的検証システムの試作研究
矢島 修三; 平石 裕実; 荻野 博幸; 武永 康彦; 浜口 清治; 高木 直史
日本学術振興会, 科学研究費助成事業 試験研究(B), 京都大学, 試験研究(B), 本研究では、時相論理に基づく論理設計の形式的検証システムについて、次の研究を行った。 (1)論理設計の形式的検証システムの試作 (a)従来形式的検証に用いられてきた分岐時間モデルに基づく時相論理に比べ、表現能力が高く、また直観的な記述が可能な線形時間時相論理を取り上げ、論理関数処理に基づく検証システムの開発・実装を行い、実例を検証し、その有効性を示した。(b)大規模回路を縮退するために開発した配列構造に基づく抽象化手法を実例に適用するには、部分回路の検証が必要であるが、従来法では、ビット数に対して指数時間の検証時間を要する乗算器が含まれているため、取り扱いが困難であった。本研究では、二分モーメントグラフと呼ばれるデータ構造を用いることで、乗算器について多項式時間での検証が可能であることを実験的に示すことに成功した。今後、配列構造に着目した抽象化手法と二分モーメントグラフに基づく手法を融合していくことが課題である。 (2)論理関数処理の高速化に関する研究 (a)二分決定グラフの処理について、論理演算、最小化の問題を取り上げ、その計算複雑度を確定した。(b)従来、論理関数処理に用いられて来た二分決定グラフの拡張とみなすことのできる、V節点を含む二分決定グラフや分岐プログラムの種々のクラスについてその表現能力を明らかにした。(c)二次記憶を用いて大規模な二分決定グラフを処理する手法を開発し、実装・実験を行ってその有効性を示した。 (3)システムのユーザインターフェースに関する研究 従来から開発してきたマルチスクリーン・マルチコンピュータシステムにXウィンドウ上での描画機能を実装し、二分決定グラフや論理回路図の描画を可能とした。, 05558030
研究期間 1993年 - 1994年 - 二分決定グラフの性質と並列処理アルゴリズムに関する研究
武永 康彦
日本学術振興会, 科学研究費助成事業 奨励研究(A), 京都大学, 奨励研究(A), 本研究では、論理設計支援の分野で論理関数の内部表現として広く利用されるなど、効率的な論理的関数の表現法として注目されている二分決定グラフについて、その論理関数の表現能力等理論的な立場からの研究をおこなった。 1.共有二分決定グラフの性質に関する研究 (1)変数割当とそれに対する論理関数値の組をいくつか与えたとき、それを満たす幅 k以下の二分決定グラフが存在するかという、二分決定グラフの最小推論問題がNP完全であることを示した。この結果から、二分決定グラフのPAC学習が不可能であることが導かれた。これは、不完全指定論理関数の二分決定グラフによる処理の複雑さを示したとも考えられる。 (2)閾値関数を表す二分決定グラフのサイズについて考察し、任意の閾値関数を表現するのに必要なサイズの上界及び下界を示した。変数の順序を固定した場合、適切な変数順序を選べる場合ともに指数的な下界が得られた。特に前者の場合においては上界と定数まで一致し、必要な二分決定グラフノサイズが完全に明らかにできた。 論理関数処理の計算複雑さに関する研究 以前からおこなっていた二分決定グラフの並列処理アルゴリズムに関する研究を進め、この成果をまとめた。また、機能メモリ上での二分決定グラフ処理手法について検討をおこなった。, 05780242
研究期間 1993年 - 1993年 - 論理関数処理の並列アルゴリズムと計算複雑さに関する研究
武永 康彦
日本学術振興会, 科学研究費助成事業 奨励研究(A), 京都大学, 奨励研究(A), 04750327
研究期間 1992年 - 1992年 - ブール関数処理による順序回路の自動合成・設計検証システムの試作研究
矢島 脩三; 平石 裕実; 荻野 博幸; 武永 康彦; 濱口 清治; 高木 直史
日本学術振興会, 科学研究費助成事業 試験研究(B), 京都大学, 試験研究(B), ブール関数処理による順序回路の自動合成・設計検証システムの試作研究に関して、以下の成果を得た。 1.ブール関数処理による順序回路の自動合成システムの試作研究順序機械を非同期式順序回路として実現するための状態割り当て方式として、単発状態割り当てとSTT(singletransition time)状態割り当てを取り上げ、ブール関数処理を利用した最小解を求めるアルゴリズムを構築し、試作した。本試作システムにより、小規模な順序機械に対しては最小解を見つけることが可能となった。 2.ブール関数処理による順序回路の設計検証システムの試作研究仕様記述言語として、従来の時相論理よりも高い表現能力を持つ分岐時間正則時相論理を用いて、ブール関数処理を利用した設計検証アルゴリズムを構築した。また、これを基にした形式的設計検証システムを試作し、マイクロプロセッサなどの実例に適用し、提案手法に基づく形式的検証の有用性を示した。 3.ブール関数の効率的処理手法に関する研究本研究の試作システムにおいて基礎となるブール関数処理について、共有二分決定グラフを取り上げ、その理論的性質を明らかにするとともに、グラフが小さくなる入力変数の順序づけを求める効率的な手法および巨大な共有二分決定グラフを扱うための2次記憶の利用を前提としたアルゴリズムを考案・実現した。 4.自動合成・設計検証システムのグラフィク・インタフェース既提案のマルチコンピュータ・マルチスクリーン・システムを、ワークステーション上に新たに実現し、自動合成・設計検証システムのインタフェースのための高解像度と高速描画を達成した。, 03555074
研究期間 1991年 - 1992年 - 共有二分決定図による論理関数の効率的処理とそれに基づく論理設計支援に関する研究
矢島 脩三; 荻野 博幸; 武永 康彦; 石浦 菜岐佐; 高木 直史; 平石 裕実; 岩間 一雄
日本学術振興会, 科学研究費助成事業 一般研究(B), 京都大学, 一般研究(B), 本研究では、論理関数の表現法、効率的処理手法の研究を行ない、その成果を種々の論理設計支援に適用した。 1.論理関数の効率的表現法及び処理手法に関する研究 共有二分決定図による論理関数の表現及び、属性エッジの提案やベクトル計算機向きのアルゴリズムの開発などその処理の効率化手法を研究した。また、ノ-ド数の少ない共有二分決定図を得る変数の順序づけの手法を研究した。 2.共有二分決定図の論理設計支援に関する研究 論理回路の故障診断、タイミング検証への応用の研究を行なった。故障診断に関しては、多重故障に対する故障シミュレ-ションの効率的計算法、効率的な故障検査系列の生成のためテスト集合の圧縮法を開発した。タイミング検証に関しては、論理回路中の素子遅延のばらつきを考慮したシミュレ-ション手法を開発した。 3.共有二分決定図を利用した論理設計検証に関する研究 状態遷移図を論理関数を用いて表現する手法を提案し、これを用いた分岐時間正則時相論理による形式的検証アルゴリズムを開発、順序機械の検証システムを実現した。 4.論理関数処理の計算複雑さに関する研究 二分決定図で効率的に表現・処理できる関数のクラスを明らかにした。また、二分決定図の処理の並列化手法を示し、その計算量を明らかにした。 5.論理設計支援システムに関する研究 論理設計支援ツ-ルにおける共有二分決定図処理を容易にするためのパッケ-ジを作成した。, 02452162
研究期間 1990年 - 1991年
学術貢献活動
- 26th Workshop on Advances in Parallel and Distributed Computational Models (APCDM2024)
学会・研究会等, 査読, 実施期間 2024年05月27日 - 2025年05月27日 - The Twelfth International Symposium on Computing and Networking
学会・研究会等, 査読, 実施期間 2024年11月26日 - 2024年11月29日 - The Eleventh International Symposium on Computing and Networking (CANDAR2023)
学会・研究会等, 査読, 実施期間 2023年11月 - 25th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2023)
学会・研究会等, 査読, 実施期間 2023年05月 - 情報処理学会 第85回全国大会
学会・研究会等, 企画立案・運営等, 実施期間 2023年03月02日 - 2023年03月04日 - The 9th International Symposium on Computing and Networking (CANDAR2021)
学会・研究会等, 査読, 実施期間 2021年 - 23rd Workshop on Advances in Parallel and Distributed Computational Models (APDCM2021)
学会・研究会等, 査読, 実施期間 2021年 - 22nd Workshop on Advances in Parallel and Distributed Computational Models (APDCM2020)
学会・研究会等, 査読, 実施期間 2020年 - The Eighth International Symposium on Computing and Networking (CANDAR2020)
学会・研究会等, 査読, 実施期間 2020年 - 21st Workshop on Advances in Parallel and Distributed Computational Models (APDCM2019)
学会・研究会等, 査読, 実施期間 2019年 - 20th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2018)
学会・研究会等, 査読, 実施期間 2018年 - The Sixth International Symposium on Computing and Networking (CANDAR2018)
学会・研究会等, 査読, 実施期間 2018年 - 19th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2017)
学会・研究会等, 査読, 実施期間 2017年 - The Fifth International Symposium on Computing and Networking (CANDAR2017)
学会・研究会等, 査読, 実施期間 2017年 - 18th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2016)
学会・研究会等, 査読, 実施期間 2016年 - 17th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2015)
学会・研究会等, 査読, 実施期間 2015年 - 14th International Conference on Algorithms and Architectures for Parallel Processing (ICA3PP2014)
学会・研究会等, 査読, 実施期間 2014年 - 16th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2014)
学会・研究会等, 査読, 実施期間 2014年 - 11th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA13)
学会・研究会等, 査読, 実施期間 2013年 - 15th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2013)
学会・研究会等, 査読, 実施期間 2013年 - 14th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2012)
学会・研究会等, 査読, 実施期間 2012年 - 13th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2011)
学会・研究会等, 査読, 実施期間 2011年 - 3rd International Workshop on Parallel and Distributed Algorithms and Applications (PDAA)
学会・研究会等, 査読, 実施期間 2011年 - 2nd International Workshop on Parallel and Distributed Algorithms and Applications (PDAA10)
学会・研究会等, 査読, 実施期間 2010年 - 12th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2010)
学会・研究会等, 査読, 実施期間 2010年 - 11th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2009)
学会・研究会等, 査読, 実施期間 2009年 - 10th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2008)
学会・研究会等, 査読, 実施期間 2008年 - 9th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2007)
学会・研究会等, 査読, 実施期間 2007年 - 8th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2006)
学会・研究会等, 査読, 実施期間 2006年 - 7th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2005)
学会・研究会等, 査読, 実施期間 2005年 - 6th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2004)
学会・研究会等, 査読, 実施期間 2004年 - 5th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2003)
学会・研究会等, 査読, 実施期間 2003年 - 4th Workshop on Advances in Parallel and Distributed Computational Models (APDCM2002)
学会・研究会等, 査読, 実施期間 2002年 - 3rd Workshop on Advances in Parallel and Distributed Computational Models (APDCM2001)
学会・研究会等, 査読, 実施期間 2001年
