Yasuhiko TAKENAGA (武永 康彦)

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2400000, indirect: 720000)
On games with onlineness, we have mainly dealt with PuyoPuyo, which is a kind of Tetris-like games. We have studied on the affect of lookahead of input pieces to the winning strategy of single-player PuyoPuyo. As a main result, we have shown that the player loses on the game board of width two or three if the number of colors used for input pieces is large, how large the number of lookaheads is.
On games on graphs, we have mainly studied on peg moving games like peg solitaire and Chinese checkers on graphs. We have proved hardness results on several problems on the games including solvabiliy of graphs on peg solitaire and deciding the winner on Chinese checkers. We have also studied on the new variation of the rules on peg moving games.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1900000, indirect: 570000)
In this research, we deal with a falling block puzzle game PuyoPuyo, which has online property, as a single-player game and consider the conditions so that the player can win, that is, the player can keep playing the game forever on the gameboard of a constant height.
We have considered both the cases that the lookahead of inputs exists as in the real game and it does not exist. In both cases, we have shown sufficient conditions that the player wins and that the player loses using the number of game pieces, the width of the gameboard and the number of lookaheads as parameters. Also we have shown that the ideas of the proofs can be applied to the other similar games.
Also, we have shown algorithms and complexity of the problems to decide if the matchstick puzzles on the grid has a solution and the problem to decide the winner of a tow-player game QUIXO.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2500000, indirect: 750000)
This research is concerned with Game Informatics. The themes are (1) computer search of And-Or trees, and (2) computational complexity of games and puzzles.
Search of And-Or tree (game-tree) by computers generally use evaluation function. We define our game-tree model, and compare numbers of configurations to be searched by depth-first search at the designated depth of our game-tree under various evaluation functions. Our result shows that the number of configurations when an evaluation function is applied, which is as close as the perfect evaluation function with probability p (0We obtained computational complexities of some games and puzzles, and the results have been published as papers, or presented in international conferences.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 1600000, indirect: 480000)
We have developed fixed-parameter algorithms or proved the hardness of vertex coloring problems on parameterized graphs obtained by adding or deleting edges from graphs in classes such as comparability graphs, permutation graphs and grid graphs. We have also developed a fixed-parameter algorithm for isomorphism of tree+ ke graphs. In addition, we have clarified the property of problems and parameterized graph classes which makes it possible to design fixed-parameter algorithms.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業 特定領域研究, Category: 特定領域研究, Fund Type: -, Overall Grant Amount: - (direct: 11200000, indirect: -)
1.二分決定グラフによるデータ表現については、第一に、二分決定グラフの構造を論理関数で表現する二分決定グラフの非明示的表現を用いて、効率的な表現が可能な論理関数について研究を行ない、多変量閾値関数を入力変数のビット長に依存しないサイズで表現できることを示した。
第二に、A07班山下との共同研究により、量子論理関数を効率よく表現するためのOBDDの変種データ構造を比較検討し、山下が以前に提案したDecisionDiagrams for Matrix Functions(DDMFs)の有効性を理論的に考察した。このデータ構造が、量子論理回路に特有の制約条件をうまく利用しており、単純なOBDDよりも一層データを圧縮し、処理効率を高めていることを明らかにした。
2.OBDDに基づくシンボリックアルゴリズムについては、前年度に引き続き、トポロジカルソートの列挙、OBDDによる画像処理アルゴリズムについて研究を行なった。前者では先行頂点数等を求めることにより従来法より計算過程でのOBDDサイズを大幅に抑えられることを示した。後者ではOBDD予測符号化を用いることによりOBDDサイズが圧縮可能であり、提案済みの画像処理アルゴリズムをほぼそのまま利用できることを示した。また、OBDDを用いたナンバーリンクの解法、問題の正当性の判定手法の提案・実装を行なった。

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2400000, indirect: -)
We introduced a restricted model of context-free tree grammars called spine grammars, and studied their formal properties including considerably simple normal forms. Recent research on natural languages has suggested that formalisms for natural languages need to generate a slightly larger class of languages than context-free grammars, and for that reason tree adjoining grammars have been widely studied relating them to natural languages. It was shown that the class of string languages generated by spine grammars coincides with that of tree adjoining grammars. We also introduced acceptors called linear pushdown tree automatas are obtained from pushdown tree automata with restriction on duplicability for the pushdown stacks. We also investigated learning theory and obtained a polynomial time inference algorithm for Moore type sequential machines. Further we also investigated the automata models for tree adjoining grammars and introduced a model called transfer pushdown automata.

Offer Organization: Japan Society for the Promotion of Science, System Name: Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), Category: Grant-in-Aid for Scientific Research (C), Fund Type: -, Overall Grant Amount: - (direct: 2100000, indirect: -)
We focus our attention on finding lower bounds of the number M(m,n) of comparators in (m,n)-merging networks. M(n,n), (n < 5,n = 7,8,9) and 16 < oM(6,6) < 17 are already known. We proved that M(6,6) = 17. (The paper is published.)
We derived a lower bound theorem concerning M(m,n), and showed that infinite-many Batcher's odd-even merge are optimal. By the theorem, we solved an open problem posed by Yao and Yao, which has been open for a quarter century. (The paper is published.)
Consider Tsume-Shogi on n x n Shogi-board. We proved that the problem to determine whether the attack-side player (the first player) can give checkmate the game is EXPTIME complete. (The paper is published.)
For a directed acyclic graph G with n nodes, T(G) is defined to be the number of the ways to assign integers 1,2, …, n to the nodes of G so that the number on node u is less than the one on v for an edge (u,v) in G. According to the definition, T(G] can be computed in O(n^2・n^!) steps. We presented an algorithm to compute T(G) in O(n^2 2^n) steps. (The paper is published in IEICE Technical Report.)
As far as other researchers are concerned, Dr. Kasai showed a polynomial time inference algorithm, and a result in formal language. Dr. Takenaga gave some properties on ordered binary decision diagrams, and on tree-shellable boolean functions. Dr. Hasunuma showed properties on graph theory, and gave some graph algorithms. These results are considered as basic studies for our research project, and we will further develop these theories in our future research.

Offer Organization: 日本学術振興会, System Name: 科学研究費助成事業 奨励研究(A), Category: 奨励研究(A), Fund Type: -, Overall Grant Amount: - (direct: 1700000, indirect: -)
本研究では、二分決定木や分岐プログラムなど理論上実際上重要な、グラフによる論理関数の表現法について、研究を行なってきた。本年度の研究成果の詳細は以下の通りである。
1. 分岐プログラムの性質と表現能力に関する研究
分岐プログラムの一種で、効率的な論理関数の表現法として知られる二分決定グラフについて、論理関数の正の例および負の例からの学習可能性について研究を行なった。具体的には、すべての例を満たす最小サイズの二分決定グラフを求める問題が、関数をしきい値関数に制限した場合でもNP困難であることを示した。
2. 論理関数双対化等への応用
前年度に提案した、論理関数を二分木表現の1つの経路が1つの素項に対応するような正論理関数のクラスについて、決定木の変数順序を固定した場合(ordered tree-shellable関数)、固定しない場合(tree-shellable関数)にわけて、さらに研究を進めた。
(Ordered)tree-shellableであることがわかれば、効率良い双対化等、その特長の活用が可能だが、それにはこれらのクラスに属するかどうかの判定が必要となる。Quadratic関数(積和形表現の各積項のリテラル数が2個)に対しては多項式時間で判定可能であるが、一般の場合についても、リテラル数が2個の積項だけを取り出した関数が(ordered)tree-shellableであることが、必要条件となることを示した。また、前年度のプログラムを改良し、変数の置換によって等価となる関数を1個とみなした場合も含め、6変数までの関数に対して、これらの性質を持つ関数の個数を具体的に求めた。