1-4 情報システム解析学科研究活動報告●学科●学科専任教員

情報システム解析学科
斎藤明（教授）鈴木理（教授）谷聖一（教授）橘貞雄（教授）戸田誠之助（教授）
夜久竹夫（教授）
谷口彰男（教授）
韓東力（准教授）

古市茂（准教授）

吉岡卓（助教）【研究の概要および結果】
本学科では学科研究費の主な使途として雑誌購入に充てています。それらの雑誌は学科共同利用設備として，各種研究課題遂行のために使われました。特に，以下の分野において多数の研究課題が得られています。
計算量理論，アルゴリズム，グラフ理論，数理情報，自然言語処理，知識情報処理，視覚言語処理，システム解
析，複素解析。
以下において，上記研究分野におけるいくつかの成果を概観いたします。
［ 視覚言語処理］
曲面グラフィックス，ボリュームグラフィックス，階層型図表のための体系的で効率の良いデータ構造を探求する事を目的とした。特に，次数が有限のデータ構造を考えてそれらに関わるアルゴリズムとそれらの性質を明らかにした。
その結果，24 次の次数を持つ，格子型グラフにもとづくデータ構造に関わる変形アルゴリズムをいくつか構成した。また，16 次の次数を持つ，多層型格子グラフに基づくデータ構造に関わる変形アルゴリズムをいくつか構成した。さらに，階層型図表のための情報構造を定めるグラフ文法を応用して，開発システムを実装した。
今後の展望としては，タグ言語による情報構造の記述が必要と思われる。また，変形アルゴリズムの設計が実装に間に合わなかったため，今後は変形アルゴリズムをさらに構成する必要がある。
（1）Takaaki Goto, Yasunori Shiono, Takeo Yaku, Kensei Tsuchida, and Tetsuro Nishino,“Hichart Development
Environment for Embedded Software”, Proceedings of Triangle Symposium on Advanced ICT 2009, UEC, Tokyo, Japan,
pp. 17-20,（ 2009）.
［グラフ理論］
グラフの 2- 正則な全域部分グラフを 2- 因子とよぶ。2009 年度はグラフの 2- 因子を主な研究対象とした。特に 2因子の存在を保証するような禁止部分グラフの性質を調べた。H をグラフの集合とし，「最小次数≧ 2，最大次数≧3 である位数が十分大きい H-free graph は 2- 因子を持つ」と命題を考え，この命題を真にするような集合 H の性質を研究した。 |H|=1 の場合には H={K1，2} が唯一の解であることが知られていたので，本研究では |H| ≧ 2 の場
14

合に H の中にスターが存在するか，存在する場合にはその位数に関してどのような情報が得られるか，という点を（b）|H|=3 の重点的に調べた。研究の結果（a）|H|=2 の場合には，その中に必ず K1，2 もしくは K1，3 が含まれる。
場合には，その中に必ずスターが含まれる。ただし，そのスターの位数には制約がなく，任意のスターK1，k に関して，ある連結グラフ F1，F2 をとると，最小次数≧ 2，最大次数≧ 3 である位数の十分大きい {K1，k，F1，F2}-free グラフは2- 因子を持つ。
（c）|H|=4 とすると，スターの制約も解消され，最小次数≧ 2，最大次数≧ 3 である位数の十分大
きい {F1，F2，F3，F4}-free グラフが 2- 因子を持つような，スターでない４つのグラフ F1，F2，F3，F4 が存在する，という事実が判明した。
本研究成果は，2- 因子の存在を保証する禁止部分グラフに関して，スターの制約がグラフの個数に関してどのように変化するかを明瞭に示している。特に，今まで禁止部分グラフには必ず K1，3 が含まれるだろうと予想されていたが，その予想は正しくなく，3 個の禁止部分グラフで既にスターの位数の制約は解消され，4 個の禁止部分グラフにおいてはスターの存在自体が不要であることが分かった。一方研究を進める内に，特に |H| ≦ 3 の場合には 2- 因子の存在を保証する禁止部分グラフ H 自体を決定できるかもしれないという感触を得た。
（1）R.E.L. Aldred, J. Fujisawa and A. Saito, Two forbidden subgraphs and the existence of a 2-factor in graphs,
Australasian Journal of Combinatorics 44（2009）235-246.
（2）A. Saito and L. Xiong, Closure, stability and iterated line graphs with a 2-factos, Discrete Mathematics 309（2009）
5000-5010.
［数理情報］
一 般 化 さ れ た Wigner-Yanase skew information に 関 連 す る 不 確 定 性 関 係 が 証 明 さ れ，Journal of MathematicalAnalysis and Applications から出版された。さらにこれに関連して，一般化された Wigner-Yanase skew information と一般化された Fisher information の関係式に関する論文も同ジャーナルに投稿中である。また，二経数拡張された相対エントロピーの公理的特徴付けに成功し，学会発表を経て，国際ジャーナルに投稿中である。
（1）S.Furuichi, On the maximum entropy principle and the minimization of the Fisher（2）informationin Tsallis statistics, Journal of Mathematical Physics, Vol.50（2009）, 013303-1 〜 013303-12.
（3）S.Furuichi, K.Kuriyama and K.Yanagi, Note on matrix trace inequalities, Linear Algebra and its Applications, Vol. 430（2009），pp.2271-2276.
（4）S.Furuichi, K.Yanagi and K.Kuriyama, Trace inequalities on a generalized Wigner-Yanase skew information, Journal of
Mathematical Analysis and Applications, Vol.356（2009），pp.179-185.
（5）S.Furuichi, On generalized Fisher informations and Cremer-Rao type inequalities, Journal of Physics: ConferenceSeries, Vol.201（2010），012016.
［知識情報処理 ］
人間の知識を表現する手法として Order-sorted Logic がある。Order-sorted Logic の記述能力は非常に高く知識情報処理の分野では広く知られている。しかし，Order-sorted Logic は一般的な名詞に対する概念階層を記述するのに優れているが，動詞や形容詞といった表現に対する階層構造を表現するには不向きである。そこで，まず Ordersorted Logic を動詞なども扱えるように拡張し，新しい論理体系を提案した。次に，それを計算機内部で処理するための代数的構造を示し，人間の知識処理に対して効果的な視覚言語 CDL を定義した。このことにより，人間の15

知識をより適切に表現しながら，計算機への実装も容易となる結果を得た。これらの成果については，国際ジャーナルへ投稿中である。
また，上記以外の研究課題に対する成果についても，次年度以降順次学会と学会論文誌等の刊行物で公表される予定です。
さらに平成 21 年度の研究活動としては，研究遂行と交流のため，以下の講演会を実施いたしました。
i.

講師：Benjamin Burton（The University of Queensland）
題目：Normal surfaces: Taming the wild algorithms of topology
日時：2010 年 2 月 18 日（木）15:00~16:00

ii.

講師：Ryan Budney（University of Victoria）
題目：3-manifolds in the 4-sphere
日時：2010 年 2 月 18 日（木）16:15 〜 17:15

iii. 講師：三枝木 宏行
題目：Max/Msp 入門〜確率論に基づく作曲〜
日時：2010 年 2 月 20 日（木）13:00~
上記講演会の実施は，研究活動に対する学術的・社会的意義を高める事に寄与し，教育や社会への貢献を達成する事ができました。
上記 i.，ii. では，R. Budney 氏（U. of Victoria）と B. Burton 氏（U. of Queensland）を招き 2 月 18 日に計算論的位相幾何学セミナーを開催しました。周知に努めた結果，6 大学から約 20 名という多くの研究者が参加し，活発な議論が行われました。Ryan 氏からは結び目の空間への埋め込みについて，Burton 氏からは 3 次元多様体の単体分割の分類に関する講義が行われ，その後参加者も含めた議論が活発に行われました。これらの議論に基づき，2 橋絡み目に対しその HOMFLY 多項式を O（n2 ）時間で決定するアルゴリズムを発案しました。この成果は，平成 22 年 6 月に電子情報通信学会コンピュテーション研究会で発表の予定です。また，iii. についても，平成 21 年度自然研共同研
究「様々な分野におけるチョムスキー言語の役割」の一環として講演会が行われました。参加者は理系のみならず文系の研究者・学生が多数参加し，質疑応答も多数あり好評のうちに終了することができました。
最後に，本学科における研究費の使途内訳を以下に示します。
・図書（図書館雑誌）

870,000 円（研究の遂行）

・ 切手

10,000 円（研究の遂行）

・ 消耗図書88,672 円（研究の遂行）

・ 講演謝金150,000 円（研究の遂行と交流）

・ ソフトウェア

103,845 円（研究成果のプレゼンと資料作成）

・ メディア，ブルーレイドライブ （研究成果の実装とソフトウェア開発）
・ プロジェクタランプ
合計（研究成果の検討と公表）
1,309,877 円

上記研究課題およびその成果に対して，予算執行が適切に行われていると考えます。

16