No.1375
計算機科学基礎理論の新展開
Evolutionary Advancement in Fundamental Theories of Computer Science
研究集会報告集
 
2004/02/02〜2004/02/04
坂部 俊樹
Toshiki Sakabe
 
目 次
 
1. An algebraic analysis of neighborhoods of cellular automata (Evolutionary Advancement in Fundamental Theories of Computer Science)---1
    京都大学(元) / メッス大学   西尾 英之助 / マルゲンシュテルン モーリス (Nishio, Hidenosuke / Margenstern, Maurice)
 
2. Log-ring size and value size of generators of subrings of polynomials over a finite field (Evolutionary Advancement in Fundamental Theories of Computer Science)---8
    京都大学(元)   西尾 英之助 (Nishio, Hidenosuke)
 
3. 分割量子セルオートマトンの一般化とその挙動について (計算機科学基礎理論の新展開)--------------------------------------------------15
    九州大学数理学研究院 / 九州大学数理学研究院 / 姫路工業大学工学研究科機械知能工学部門   井口 修一 / 溝口 佳寛 / 乾 徳夫 (Inokuchi, Shuichi / Mizoguchi, Yoshihiro / Inui, Norio)
 
4. 非同期セル空間における論理回路構成 (計算機科学基礎理論の新展開)------------------------------------------------------------------22
    広島大学工学研究科 / 広島大学工学研究科   斉 金山 / 森田 憲一 (Qi, Jin-Shan / Morita, Kenichi)
 
5. Canonical Data Structure for Probe Interval Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)--------28
    駒澤大学文学部自然科学教室   上原 隆平 (Uehara, Ryuhei)
 
6. A Linear-Time Algorithm for 7-coloring 1-planar Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)----35
    東京電機大学理工学部数理科学科 / 東京電機大学理工学部数理科学科   陳 致中 / 河野 光治 (Chen, Zhi-Zhong / Kouno, Mitsuharu)
 
7. Computing Phylogenetic Roots with Bounded Degrees and Errors is Hard (Evolutionary Advancement in Fundamental Theories of Computer Science)---42
    東京電機大学理工学部 / 東京電機大学理工学部   築地 立家 / 陳 致中 (Tsukiji, Tatsuie / Chen, Zhi-Zhong)
 
8. Approximating Vertex Cover on Dense Graphs (Evolutionary Advancement in Fundamental Theories of Computer Science)----------------49
    京都大学情報学研究科 / 京都大学情報学研究科   今村 友和 / 岩間 一雄 (Imamura, Tomokazu / Iwama, Kazuo)
 
9. 最大マッチングを利用したタスクスケジューリングアルゴリズムの近似度の改善について (計算機科学基礎理論の新展開)--------------------61
    三重大学工学部 / 三重大学工学部 / 三重大学工学部 / 三重大学工学部 / 三重大学工学部   加藤 雅之 / 大山口 通夫 / 太田 義勝 / 新美 信之助 / 山本 浩平 (Kato, Masayuki / Oyamaguchi, Michio / Ohta, Yoshikatsu / Niimi, Shinnosuke / Yamamoto, Kouhei)
 
10. オンライン問題の競合比解析の自動化について (計算機科学基礎理論の新展開)---------------------------------------------------------68
    京都大学情報学研究科 / 京都大学情報学研究科 / 京都大学情報学研究科   正西 申悟 / 堀山 貴史 / 岩間 一雄 (Masanishi, Shingo / Horiyama, Takashi / Iwama, Kazuo)
 
11. On generating instances for MAX2SAT with optimal solutions (Evolutionary Advancement in Fundamental Theories of Computer Science)---78
    東京工業大学情報理工学研究科数理・計算科学専攻   山本 真基 (Yamamoto, Masaki)
 
12. 議席配分法に対する線形時間アルゴリズム (計算機科学基礎理論の新展開)-------------------------------------------------------------85
    山口大学工学部 / 山口大学工学部   伊藤 暁 / 井上 克司 (Ito, Akira / Inoue, Katsushi)
 
13. Alternating CFG 再び : 新旧種とその特徴付け (計算機科学基礎理論の新展開)--------------------------------------------------------92
    早稲田大学教育学部 / カッセル大学 / カッセル大学 / カッセル大学   守屋 悦朗 / / / (Moriya, Etsuro / Hofbauer, Dieter / Huber, Maria / Otto, Friedrich)
 
14. 線形言語のある部分言語族に対する質問と特徴的なサンプルによる多項式時間学習アルゴリズム (計算機科学基礎理論の新展開)-------------99
    東京農工大学工学部情報コミュニケーション工学科 / 東京農工大学工学部情報コミュニケーション工学科 / 東京農工大学工学部情報コミュニケーション工学科   但馬 康宏 / 小谷 善行 / 寺田 松昭 (Tajima, Yasuhiro / Kotani, Yoshiyuki / Terada, Matsuaki)
 
15. Polynomial-Time Identification of an Extension of Very Simple Grammars from Positive Data (Evolutionary Advancement in Fundamental Theories of Computer Science)---106
    東京大学学際情報学府   吉仲 亮 (Yoshinaka, Ryo)
 
16. 大規模木構造データからの頻出無順序木パターン発見アルゴリズム (計算機科学基礎理論の新展開)--------------------------------------113
    九州大学システム情報科学府・研究院 / 九州大学システム情報科学府・研究院 / 九州大学システム情報科学府・研究院 / 国立情報学研究所 / 群馬大学工学部   浅井 達哉 / 房延 慎二 / 有村 博紀 / 宇野 毅明 / 中野 眞一 (Asai, Tatsuya / Fusanobu, Shinji / Arimura, Hiroki / Uno, Takeaki / Nakano, Shin-ichi)
 
17. データの論理的解析における正関数発見の並列化 (計算機科学基礎理論の新展開)------------------------------------------------------120
    九州大学システム情報科学府情報工学専攻 / 九州大学システム情報科学研究院情報工学部門 / 九州大学システム情報科学研究院情報工学部門 / 九州大学システム情報科学研究院情報工学部門   片岡 博幸 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史 (Kataoka, Hiroyuki / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)
 
18. Minimum Universal Evaluation Tree for Boolean Circuits (Evolutionary Advancement in Fundamental Theories of Computer Science)---126
    九州大学システム情報科学府 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院   牧山 幸史 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史 (Makiyama, Koji / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)
 
19. 積項の長さに制限を付けた論理関数のOrdered Tree-Shellability (計算機科学基礎理論の新展開)---------------------------------------130
    電気通信大学電気通信学研究科情報工学専攻 / 電気通信大学電気通信学部情報工学科   東海林 貴司 / 武永 康彦 (Toukairin, Takashi / Takenaga, Yasuhiko)
 
20. 決定グラフを用いた二線式単一磁束量子回路の論理設計法 (計算機科学基礎理論の新展開)----------------------------------------------137
    名古屋大学情報科学研究科情報システム学専攻 / 名古屋大学情報科学研究科情報システム学専攻 / 名古屋大学情報科学研究科情報システム学専攻   小畑 幸嗣 / 高木 一義 / 高木 直史 (Obata, Koji / Takagi, Kazuyoshi / Takagi, Naofumi)
 
21. Multi-modal logicsにおけるShannonの標準形展開の自然な拡張 (計算機科学基礎理論の新展開)-----------------------------------------144
    椙山女学園大学   大芝 猛 (Oshiba, Takeshi)
 
22. 線形制約式を用いた時間QoS一貫性の検証法 (計算機科学基礎理論の新展開)-----------------------------------------------------------151
    大阪大学情報科学研究科 / 大阪大学情報科学研究科 / 大阪大学情報科学研究科   岡野 浩三 / 森 一夫 / 谷口 健一 (Okano, Kozo / Mori, Kazuo / Taniguchi, Kenichi)
 
23. ($n-t$)-out-of-$n$しきい値付きリング署名 (計算機科学基礎理論の新展開)----------------------------------------------------------158
    東京工業大学情報理工学研究科数理・計算科学専攻 / 東京工業大学情報理工学研究科数理・計算科学専攻   一色 寿幸 / 田中 圭介 (Isshiki, Toshiyuki / Tanaka, Keisuke)
 
24. 同じ値域をもつRSA関数族の構成 (計算機科学基礎理論の新展開)---------------------------------------------------------------------164
    東京工業大学情報理工学研究科数理・計算科学専攻 / 東京工業大学情報理工学研究科数理・計算科学専攻   林 良太郎 / 田中 圭介 (Hayashi, Ryotaro / Tanaka, Keisuke)
 
25. 直角二等辺三角形の二等分割とその頂点数について (計算機科学基礎理論の新展開)----------------------------------------------------171
    新潟大学総合情報処理センター / 新潟大学総合情報処理センター   三河 賢治 / 長谷川 誠 (Mikawa, Kenji / Hasegawa, Makoto)
 
26. Fast Algorithms for Computing Jones Polynomials of Certain Links (Evolutionary Advancement in Fundamental Theories of Computer Science)---174
    日本大学総合基礎科学研究科 / 東海大学理学部情報数理学科 / 中央大学理工学部数学科 / 日本大学文理学部情報システム解析学科   村上 雅彦 / 原 正雄 / 山本 慎 / 谷 聖一 (Murakami, Masahiko / Hara, Masao / Yamamoto, Makoto / Tani, Seiichi)
 
27. バンド幅問題に対する遺伝的アルゴリズムの交叉方法の提案 (計算機科学基礎理論の新展開)--------------------------------------------181
    群馬大学工学部 / 群馬大学工学部   佐藤 竜也 / 山崎 浩一 (Sato, Tatsuya / Yamazaki, Koichi)
 
28. Procedures for Multiple Input Functions with DNA Strands (Evolutionary Advancement in Fundamental Theories of Computer Science)---188
    九州工業大学情報工学研究科 / 九州工業大学情報工学研究科   上尾 智史 / 藤原 暁宏 (Kamio, Satoshi / Fujiwara, Akihiro)
 
29. 楕円曲線上のスカラー倍計算の効率化 : ヤコビアン座標系上での直接計算法の提案 (計算機科学基礎理論の新展開)-----------------------195
    名古屋大学工学研究科 / 名古屋大学工学研究科   安達 大亮 / 平田 富夫 (Adachi, Daisuke / Hirata, Tomio)
 
30. A Multiplication/Division VLSI Algorithm for Modular Arithmetic (Evolutionary Advancement in Fundamental Theories of Computer Science)---201
    名古屋大学情報科学研究科 / 名古屋大学情報科学研究科   貝原 マルセロ / 高木 直史 (Kaihara, Marcelo E. / Takagi, Naofumi)
 
31. On the generative power of an extension of minimal linear grammars (Evolutionary Advancement in Fundamental Theories of Computer Science)---208
    早稲田大学教育学研究科   小野寺 薫 (Onodera, Kaoru)
 
32. Mining Indirect Association Rules (Evolutionary Advancement in Fundamental Theories of Computer Science)-----------------------214
    大阪府立大学理学系研究科 / 大阪府立大学総合科学部 / 大阪府立大学総合科学部   濱野 慎一 / 向内 康人 / 佐藤 優子 (Hamano, Shinichi / Mukouchi, Yasuhito / Sato, Masako)
 
33. SHシステムと拡張オートマトン (計算機科学基礎理論の新展開)----------------------------------------------------------------------221
    大阪府立大学理学系研究科 / 大阪府立大学総合科学部 / 大阪府立大学総合科学部   高石 理恵 / 向内 康人 / 佐藤 優子 (Takaishi, Rie / Mukouchi, Yasuhito / Sato, Masako)
 
34. On Strategies of Update Networks (Evolutionary Advancement in Fundamental Theories of Computer Science)------------------------229
    東京工業大学理学部情報科学科   梅野 真也 (Umeno, Shinya)
 
35. The Joinability and Unification Problems for Confluent Semi-Constructor TRSs (Evolutionary Advancement in Fundamental Theories of Computer Science)---233
    三重大学工学部 / 三重大学工学部 / 三重大学工学部 / 三重大学工学部   三橋 一郎 / 大山口 通夫 / 太田 義勝 / 山田 俊行 (Mitsuhashi, Ichiro / Oyamaguchi, Michio / Ohta, Yoshikatsu / Yamada, Toshiyuki)
 
36. Persistence of Termination for Overlay Term Rewriting Systems (Evolutionary Advancement in Fundamental Theories of Computer Science)---240
    島根大学総合理工学部   岩見 宗弘 (Iwami, Munehiro)
 
37. 左辺が一致するオーバレイ性を持つ左線形TRSの正規化戦略 (計算機科学基礎理論の新展開)---------------------------------------------247
    名古屋大学工学部 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科 / 名古屋大学情報科学研究科   水野 健一 / 草刈 圭一朗 / 酒井 正彦 / 坂部 俊樹 (Mizuno, Ken'ichi / Kusakari, Keiichiro / Sakai, Masahiko / Sakabe, Toshiki)
 
38. 人間指向型汎用類推証明システムの開発 (計算機科学基礎理論の新展開)--------------------------------------------------------------253
    九州工業大学情報工学研究科 / 九州工業大学情報工学部 / 九州工業大学情報工学部 / 九州工業大学情報工学部   尹 淑萍 / 山田 敬三 / 平田 耕一 / 原尾 政輝 (Yin, Shuping / Yamada, Keizo / Hirata, Kouichi / Harao, Masateru)
 
39. 移動系における最大個数巡回アルゴリズム (計算機科学基礎理論の新展開)------------------------------------------------------------260
    九州工業大学情報工学研究科情報科学専攻 / 九州産業大学情報科学部社会情報システム学科 / 九州工業大学情報工学部システム創成情報工学化 [工学科]   下入佐 真一 / 朝廣 雄一 / 宮野 英次 (Shimoirisa, Shinichi / Asahiro, Yuichi / Miyano, Eiji)
 
40. 置換グラフ上における最小節点ランキング全域木問題を解くアルゴリズム (計算機科学基礎理論の新展開)--------------------------------267
    徳島大学総合科学部自然システム学科数理科学 / 豊橋技術科学大学知識情報工学系   中山 慎一 / 増山 繁 (Nakayama, Shin-ichi / Masuyama, Shigeru)
 
41. A Dynamic Reconfiguration Tolerant Self-stabilizing Token Circulation Algorithm in Ad-Hoc Networks (Evolutionary Advancement in Fundamental Theories of Computer Science)---274
    広島大学工学研究科 / 九州大学システム情報科学研究院   角川 裕次 / 山下 雅史 (Kakugawa, Hirotsugu / Yamashita, Masafumi)
 
42. 匿名ネットワーク上のリーダー選出問題の空間計算量 (計算機科学基礎理論の新展開)--------------------------------------------------282
    九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院 / 九州大学システム情報科学研究院   安藤 映 / 小野 廣隆 / 定兼 邦彦 / 山下 雅史 (Ando, Ei / Ono, Hirotaka / Sadakane, Kunihiko / Yamashita, Masafumi)