No.790
理論計算機科学とその周辺
　
1992/01/29〜1992/01/31
高浪 五男
Itsuo Takanami
　
目　次
　
1. A Relationship between nondeterministic Turing machines and 1-inkdot Turing machines with small space-----------------------------1
　　　　Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University / Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University / Department of Computer Science and Systems Engineering, Faculty of Engineering, Yamaguchi University　　　井上 克司 / 伊藤 暁 / 高浪 五男　(Inoue, Katsushi / Ito, Akira / Takanami, Itsuo)
　
2. コオペレーティング1方向カウンタ機械システム(理論計算機科学とその周辺)-------------------------------------------------------------8
　　　　山口大学工学部 / 山口大学工学部 / 山口大学工学部　　　王 踊 / 井上 克司 / 高浪 五男[他]　(Wang, Yue / Inoue, Katsushi / Takanami, Itsuo)
　
3. 非決定性有限オートマトンの状態数最小化(理論計算機科学とその周辺)-----------------------------------------------------------------15
　　　　京都大学工学部 / 京都大学工学部　　　仙石 浩明 / 矢島 脩三　(SENGOKU, Hiroaki / YAJIMA, Shuzo)
　
4. 決定木構成問題と学習可能性(理論計算機科学とその周辺)-----------------------------------------------------------------------------22
　　　　東京工業大学理工学研究所情報工学専攻　　　小柴 健史　(Koshiba, Takeshi)
　
5. 計算データからの論理回路の構成(理論計算機科学とその周辺)-------------------------------------------------------------------------29
　　　　九州大学大学院総合理工学研究科情報システム学専攻　　　下薗 真一　(Shimozono, Shinichi)
　
6. A generalization of $\epsilon$-approximations and its application : Extended abstract--------------------------------------------36
　　　　Department of Information Science, Faculty of Science, University of Tokyo / Department of Information Science, Faculty of Science, University of Tokyo　　　Hasegawa, Susumu / Kakihara, Ken-ichiro
　
7. 根方向型語彙機能文法に基づく構文解析プログラムの実現(理論計算機科学とその周辺)---------------------------------------------------43
　　　　東京電機大学理工学部情報科学科 / 東京電機大学理工学部情報科学科 / 東京電機大学理工学部情報科学科　　　山田 節夫 / 西野 哲朗 / 米田 信夫　(Yamada, Setsuo / Nishino, Tetsuro / Yoneda, Nobuo)
　
8. 根方向型語彙機能文法の正データからの学習(理論計算機科学とその周辺)---------------------------------------------------------------50
　　　　東京電機大学理工学部情報科学科 / 東京電機大学理工学部情報科学科 / 東京電機大学理工学部情報科学科　　　清水 直昭 / 西野 哲朗 / 一松 信　(Shimizu, Naoaki / Nishino, Tetsuro / Hitotsumatsu, Shin)
　
9. 3SAT問題のニューラルネットワーク解法(理論計算機科学とその周辺)-------------------------------------------------------------------57
　　　　広島大学工学部 / 広島大学工学部 / 広島大学工学部　　　近松 良知 / 山下 雅史 / 阿江 忠　(CHIKAMATSU, Yoshitomo / YAMASHITA, Masafumi / AE, Tadashi)
　
10. インプリサイスコンピュテーション手法に対するスケジューリングアルコリズム(理論計算機科学とその周辺)------------------------------64
　　　　広島大学工学部 / 広島大学工学部　　　小笠原 秀和 / 若林 真一　(OGASAWARA, Hidekazu / WAKABAYASHI, Shin'ichi)
　
11. Competitive Analysis of Round Robin Algorithm-----------------------------------------------------------------------------------71
　　　　東京大学情報科学科　　　松本 剛　(Matsumoto, Tsuyoshi)
　
12. malign measureによるa priori measureの特徴づけについて(理論計算機科学とその周辺)------------------------------------------------78
　　　　東京工業大学理学部　　　小林 孝次郎　(Kobayashi, Kojiro)
　
13. 木構造図式の描画問題(理論計算機科学とその周辺)----------------------------------------------------------------------------------85
　　　　関東学園大学経済学部　　　安斎 公士　(Anzai, Koushi)
　
14. セル構造オートマトンに基づく並列アレイ生成システム(理論計算機科学とその周辺)----------------------------------------------------95
　　　　山形大学工学部 / 山形大学工学部　　　上野 聡 / 森田 憲一　(Ueno, Satoshi / Morita, Kenichi)
　
15. 正規アレイ文法に非空白記号を検出する能力を与えた文法について(理論計算機科学とその周辺)-----------------------------------------102
　　　　鳥取大学工学部 / 鳥取大学工学部 / 鳥取大学工学部　　　谷口 弘 / 菅田 一博 / 清水 忠昭[他]　(TANIGUCHI, Hiroshi / SUGATA, Kazuhiro / SHIMIZU, Tadaaki)
　
16. 高階アブストラクションに基づく自然演繹証明の類推(理論計算機科学とその周辺)-----------------------------------------------------109
　　　　Department of Artifical Intelligence, Kyushu Institute of Technology　　　原尾 政輝　(HARAO, Masateru)
　
17. サーカムスクリプションと安定モデル意味論(理論計算機科学とその周辺)-------------------------------------------------------------116
　　　　九州大学総合理工学研究科情報システム学専攻　　　平田 耕一　(Hirata, Kouichi)
　
18. 自動証明における自然な証明生成の1アルゴリズム(理論計算機科学とその周辺)--------------------------------------------------------125
　　　　名古屋工業大学　　　大芝 猛　(Oshiba, Takeshi)
　
19. 二分決定グラフの並列構成アルゴリズムについて(理論計算機科学とその周辺)---------------------------------------------------------134
　　　　神戸大学工学部 / 神戸大学工学部 / 神戸大学工学部　　　木村 晋二 / 井垣 努 / 羽根田 博正
　
20. 二分決定グラフによる論理関数処理の計算複雑さ(理論計算機科学とその周辺)---------------------------------------------------------141
　　　　京都大学工学部 / 京都大学工学部　　　武永 康彦 / 矢島 脩三　(TAKENAGA, Yasuhiko / YAJIMA, Shuzo)
　
21. 色塗り分け問題がP完全又はNCになる為の十分条件について(理論計算機科学とその周辺)------------------------------------------------148
　　　　九州大学工学部 / 九州大学工学部　　　岩本 宙造 / 岩間 一雄　(Iwamoto, Chuzo / Iwama, Kazuo)
　
22. Deciding whether Graph $G$ Has Page Number One is in NC------------------------------------------------------------------------155
　　　　豊橋技術科学大学知識情報工学系 / NTT基礎研究所　　　増山 繁 / 内藤 昭三　(MASUYAMA, Shigeru / NAITO, Shozo)
　
23. 平面オイラーグラフの辺素な路問題を解く並列アルゴリズム(理論計算機科学とその周辺)-----------------------------------------------162
　　　　豊橋技術科学大学知識情報工学系 / 豊橋技術科学大学知識情報工学系　　　中山 慎一 / 増山 繁　(NAKAYAMA, Shin-ichi / MASUYAMA, Shigeru)
　
24. 確率付グラフ上の点素なs-t Disjoint Pathsの期待最大本数の計算問題(理論計算機科学とその周辺)-------------------------------------169
　　　　豊橋技術科学大学知識情報工学系 / 豊橋技術科学大学知識情報工学系　　　程 鵬 / 増山 繁　(CHENG, Peng / MASUYAMA, Shigeru)
　
25. 歩行を実現するグラフ構成問題について(理論計算機科学とその周辺)-----------------------------------------------------------------175
　　　　九州大学大学院総合理工学研究科　　　丸山 修　(Maruyama, Osamu)
　
26. ネットワークの対称性と、$k$-LEADER(S)の計算能力(理論計算機科学とその周辺)------------------------------------------------------194
　　　　東京工業大学理学部　　　坂本 直志
　
27. 情報散布方式の一般的記述と自己同型写像(理論計算機科学とその周辺)---------------------------------------------------------------201
　　　　Mathematik-Informatik, Universitat GH-Paderborn / Department of Computer Science, Gunma University / Department of Computer Science, Gunma University　　　Unger Walter / 五十嵐 善英 / 大澤 新吾　(Unger, Walter / Igarashi, Yoshihide / Osawa, Shingo)
　
28. 平衡弱合流性と項書換えシステムの正規戦略(理論計算機科学とその周辺)-------------------------------------------------------------208
　　　　NTT Laboratories　　　外山 芳人　(Toyama, Yoshihito)
　
29. LOTOSによる分散システムの全体記述と各ノードの動作記述 : 等価性と変換アルゴリズムについて(理論計算機科学とその周辺)-------------215
　　　　大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科 / 大阪大学基礎工学部情報工学科　　　東野 輝夫 / 安本 慶一 / 谷口 健一　(Higashino, Teruo / Yasumoto, Keiichi / Taniguchi, Kenichi)
　
30. 高次の動的Voronoi図とその応用(理論計算機科学とその周辺)------------------------------------------------------------------------222
　　　　津田塾大学学芸学部数学科 / 東京大学理学部情報科学科　　　今井 桂子 / 今井 浩　(Imai, Keiko / Imai, Hiroshi)
　
31. 包除原理による和集合のサイズの評価について(理論計算機科学とその周辺)-----------------------------------------------------------229
　　　　東北大学工学部情報工学科 / 東北大学工学部情報工学科　　　神保 秀司 / 丸岡 章　(JINBO, Shuji / MARUOKA, Akira)
　
32. Semirigid sets of clones of quasi-linear functions over a finite domain--------------------------------------------------------236
　　　　International Christian University / Electrotechnical Laboratory / International Christian University　　　野崎 昭弘 / 宮川 正弘 / ポゴシャン G.　(Nozaki, Akihiro / Miyagawa, Masahiro / Pogosyan, Grant)
　
33. Complexity of decision trees for Boolean operators : a shortened version-------------------------------------------------------242
　　　　Inst. of Math. and Comp. Sci., University of Latvia / Electrotechnical Laboratory　　　フレイヴァルト R. / 宮川 正弘　(Freivalds, Rusins / Miyagawa, Masahiro)
　
34. The Feedback Operation in Functional Systems of Automata-----------------------------------------------------------------------249
　　　　Department of Computer Science, The University of Electro-Communications　　　Lashkia, V.
　
35. Affine型合同反復模型の状態遷移図について(理論計算機科学とその周辺)-------------------------------------------------------------256
　　　　九州大学理学部 / 九州工業大学情報工学部　　　隈本 覚 / 乃美 正哉　(Kumamoto, Satoru / Nohmi, Masaya)
　
36. 非線形項書き換えシステムのE-非オーバーラップ性について(理論計算機科学とその周辺)-----------------------------------------------263
　　　　名古屋工業大学 / 三重大学 / 名古屋工業大学　　　張 磊 / 大山口 通夫 / 伊藤 英則　(Zhang, Lei / Oyamaguchi, Michio / Itoh, Hidenori)
　
37. Logspace Bounded Alternation and Logical Query Programs------------------------------------------------------------------------269
　　　　Department of Information Science, Kyoto University / Department of Information Science, Kyoto University　　　岡部 寿男 / 津田 孝夫　(OKABE, Yasuo / TSUDA, Takao)