* た f/rt
発 弼 霧
穿 話 , 数理解析研究所講究録 790
ダ鍔
理論計算機科学とその周辺
禁帯出期間
6a. i?. 20 一 7. 1 2 i
g
数研図書室 1
p一一e一一一一一tbov一一p一一一e-v..一一.Hor一..r}
京都大学数理解析研究所
1992 年 6 月
/6
理論計算機科学とその周辺 研究集会報告集
1992年1月29日{}˜1月31日
研究代表者 高浪 五男(Itsuo Takanam1)
目次
繭 q 蔀盤籔 斯馨盤融 理爺箋
mg machines with small space
山口大工 井上 克司 (Katsushi lnoue) 山口大工 伊藤 暁 (Aklla Ito) 山口大工 高浪 五男(ltsuo Takanami) 2コオペレーティング1方向カウンタ機械システム
山口大工 王 躍 (Wang Yue) 山口大工 井上 克司(Katsuslu lnoue) 山口大工 高浪 五男(ltsuo Takanam1) 大島商船高専 松野 浩嗣(Hnoshi Matsuno) 3非決定性有限オートマトンの状態数最小化
京大工 仙石 浩明 (Hnoaki Sengoku) 京大工 矢島 脩三 (Shuzo YaJnma) 4 決定木構成問題と学習可能性 ,
東工大 小柴 健史(Takeshl I〈oshiba) 5計算データからの論理回路の構成
九大 下薗 真一 (Shln ichi Shlniozono) 6 A geneialization of E-appio3cimations and its apphcation
東大理 長谷川進 (Susumu Hasegawa) 東大理 柿原 謙一郎(Ken 1chllo I〈aklhala) 7根方向型語彙機能文法に基づく構文解析プログラムの実現
東京電機大 山田 節夫(Setsuo Yamada) 東京電機大 西野 哲朗(Tetsulo Nlshlno) 東京電機大 米田 信夫(Nobuo Yoneda)
1 A Relationslnp between nondetei mmistic Tunng machmes and 1-mkdot Tui-
1
8
15
22
29
36
43
1
8根方向型語彙機能文法の正デh.一ptbタからの学習... . .... . 50 東京電機大 清水 直昭(Naoaki Shnmlzu)
東京電機大 西野 哲朗(Tetsuio Nishino) 東京電機大 ・・・・・・・…松 信(Shln Hltotsumatsu) 9 3SAT 問題のニューラルネットワー…eク解法 . . ...57
広大工 近松 良知(Yoshitomo Chikamatsu) 広大工 山下 雅史(Masafum1 Yamashita) 広大工 阿江 忠 (Tadashl Ae)
10. Scheduhng Algorithms foi lmpiecise Computations . . . ... . . . 64 広大工 小笠原 秀和(Hldekazu Ogasawal a) 広大工 若林 真一(Shnn ichl Wakabayashl) 11 Competitive Analysis of Round Robm Algollthm .. .. . .. .. 71
東大理 松本 剛(Tsuyoshi Matsumoto) 12malign measureによるa pllorl measureの特徴づけについて .. 78
東工大理 小林 孝次郎(Kojllo Kobayash1) 13. 木構造図式の描画問題... .. 。... .85
関東学園大 安斎 三士(Koushi Anzai)
14セル構造オートマトンに基づく並列アレイ生成システム... .95 山形大工 上野 聡 (Satoshn Ueno)
山形大工 森田 憲一 (Ken 1chi Mollta)
15正規アレイ文法に非空白記号を検出する能力を与えた文法について102 鳥取大工 谷口 弘(Hn oshl Tamguchll)
鳥取大工 菅田 一博(Kazuhno Sugata) 鳥取大工 清水 忠昭(Tadaaki Shm lzu) 鳥取三洋電気 角野 秀典(Hldelloll Kadollo)
16.高階アブストラクションに基づく自然演繹証明の類推... 109 九工大情報工 原尾 政輝(Masateru Hal ao)
17サーカムスクリプションと安定モデル意味論 ... . 116 九大 平田 耕一 (Kouichi Hllata)
19二分決定グラフの並列構成アルゴリズムについて
神大工 木村 晋二(ShinJi Kiniula) 神大工 井垣 努(Tsutomu Igak1) 神大工 羽根田 博正(Hn omasa Haneda) 20二分決定グラフによる論理関数処理の計算複雑さ
京大工 武永 康彦 (Yasuhiko Takemaga) 京大工 矢島 脩三(Shuzo YaJlma) 21色塗り分け問題がP完全又はNCになる為の十分条件について
九大工 岩本 宙造 (Chuzo Iwamoto) 九大工 岩間 一雄 (Kazuo Iwama)
22 Decidmg whethei Giaph G Has Page Numbei One is m NC
豊橋技科大 増山 繁(S111gelu Masuyama) NTT基礎研 内藤 昭三(Shozo Nalto) 23平面オイラーグラフの辺素な路問題を解く並列アルゴリズム
豊橋技科大 中山 慎一 (Shm 1ch1 Nakayama) 豊橋技科大 増山 繁(Shigeiu Masuyama) 24確率付グラフ上の点素なs-t DisJoint Pathsの期待最大本数の計算問題
豊橋技科大 程鵬 (Peng Cheng) 豊橋技科大 増山 繁(Shigeiu Masuyama) 25歩行を実現するグラフ構成問題について
九大 丸山 修 (Osamu Mai uyama) 26ネノトワー・nクの対称性と、k-LEADER(S)の計算能力
東工大理 坂本 直志(Naosh1 Sakamoto)
134
141
148
155
162
169
175
194
27 A General Descmption of an lnformation Disseminatmg Scheme and lts Au-
tomoiphism 201
Umveisit a t GH-Padeiboin W Ungei
群馬大工 五十嵐 善英 (Yoshihide lgai ash1) 群馬大工 大澤 新吾 (Shmgo Osawa) 28平衡弱合流性と項書換えシステムの正規戦略 208
NTT 研 外山芳人(Yoshihito Toyama)
111
29LOTOSによる分散システムの全体記述と各ノードの動作記述 一一・p等価性iと変換アルゴリズムについて一一一一
阪大基礎工 阪大基礎工 阪大基礎工
30高次の動的VOIOIIo1図とその応用 津田塾大
東大理
野本口
東安谷
輝夫(Teiuo Higashmo) 慶一(Kellchl Yasumoto) 健一(Ken,ichi Taniguchi)今井 桂子(Kelko Imaユ) 今井浩(H1・・sh11ma1)
215
222
31包除原理による和集合のサイズの評価について 229 東北大工 神保 秀司(ShUJ i J nml)o)
東北大工 丸岡 章 (Akna Mal uoka)
32 Semingid sets of clones of quasi-hneai functions ovei a fimte domain 236 国際基督教大 野崎 昭弘(Akihn o Nozak1)
国際基督教大 G.Pogosyan
電総研 宮川 正弘(Masahn o Miyakarva) モントリオール大 1.Rosenbei9
33 Complexity of decision trees foi Boolean opei atois . . 242 Umvei sity of Latvia R Fi ei valds
電総研 宮川 正弘(Masahn o Mlyakawa) 34 The Feedback Opeiation m Functional Systems of Automata 249
電通大 V:Lashkla
35Affine 型合同反復模型の状態遷移図について 256
九大理 隈本 覚 (SatOiU Kumamoto) 九工大情報工 乃父 正哉(Masaya Nohm1)
36非線形項書き換えシステムのE一非オーバラソブ性について 263 名工大 張 轟 (Ral Chou)
三重大 大山口 通夫(Michlo Ohyama8uchi) 名工大 伊藤 英則(Hldenon lto)
