レ { 列 00
数理解析研究所講究録 695
計算アルゴリズムと 計算量の基礎理論
禁帯露期間 ie 7.26 一 8e 2 数研図書室
京都大学数理解析研究所
一 rg89 年 6 月
ガ
- ⊥ 0 乙 0 θ 4 に」 2U ワー
京都入学 90e9 3691 計算ア加リスムと計輯の鍵理論 図書
研究集会報告集
洗晒工析研究所
1989年1月30日{}˜2月1日
研究代表者 中村 昭(Aklra Nakamura)
目 次
Grammars on the hexagonal array 1
広大 工 会沢 邦夫(Kunlo Alzawa)
高々スター次数 2 の拡張正規表現 11 豊:橋技科大 劉 僖根(Heekeun Yoo)
豊橋技科大 橋口 攻三郎(Kosaburo Hashlguch1) ある拡張文法/オートマトノに関するコメノト 21
東京女大 文理 守屋 悦朗(Etsuro Morlya)
2NPDA によるノミュレーノヨノと未解決問題 27
東侮大 計算セ 岩田 茂樹(Shlgekl Iwata) 電通大 笠井 琢美(Takuml Kasa1)
線形セル構造オートマトノにおける局所関数の群の同型定理について37 東洋大 工 佐藤 忠一(Tadakazu Sato)
On Learning Equal Matrix Languages 45 富士通 高田 裕志(YUJI Takada)
木構造図式の美的描画について 55
東侮大 計算セ 郷 信義(Nobuyoshi Go) 富士通 岸本 美紀(Mlkl Klshlmoto) 東侮大 計算セ 小倉 耕一(Kolch10gura)
日本電機 土田 賢省(Kensel Tsuchlda) 東電機大 理工 夜久 竹夫(Takeo Yaku)
一1一
8
9
0 1
1 1
利用者インタフェースとしての文字自動配置機能
九大 工 今井 浩(Hlroshl Ima1) 九大 工 青沼 裕美(Hlroml Aomuma) 九大 工 加藤 研児(KenJl Kato) 九大 工 神代 伸彦(KOJlro Nobuhlko) 九大工 上林彌彦(Yahlko Kambayash1)
Declslon Problem for a Lo91c of Temporal Informatlon
広大 工 高 建明(Jlan-Mlng Gao) 広大 工 中村 昭(Aklra Nakamura)
S-bases of Boolean Functlons Under Several Functlonal
Constructlons-A Survey一
電総研 宮川 正弘(Masahlro臨yakawa)
Ottawa大 Ivan StoJmenov16 Novl Sad大 Ratko Toslcク
電総研 三島 健稔(Taketoshl Mlshlma)
高階論理ユニフィケーノヨノを用いた知識処理
山形大 工 原尾 政輝(Masateru Harao) 山形大 工 岩沼 宏冶(KOJ 1 Iwanuma) 山形大 工 三島=eseeaketfish3 thsirma)
京大 工 宇野 裕之(Yushl Uno)
京大 工 茨木 俊秀(Toshlhlde Ibarak1)
集合制約質問の記述方法およひ計算量
九大 工 岩井原 瑞穂(Mlzuho Iwaihara) 九大 工 上林 彌彦(Yahlko Kambayash1)
一11一
65
75
5 8
98
12C 。 mplexlty 。 f the 。 ptlmum J 。 1n 。 rder Pr 。謙論陣 v ぎ臨 s 誌』例 08
1 3 115
4 1
5 1
1 6
ワー 001
一の己一↓
0 σ nU111
↓の織り乙
22
多重記情階層のもとてのチータの変更を考膚した最適へ一ノノク125 九大工 掛下哲郎(Tetsuro Kakeshlta) 九大 工 上林 彌彦(Yahlko Kambayash1) 複数の階層に基づくチータへ一スの設計 135
九大 大型セ 古川 哲也(Tetsuya Furukawa) 九大工 上林彌彦(Yahlko Kambayashi) Indexing Functions and Time Lower Bounds for Sorting on
a Mesh-Connected Computer 145 Kentucky大 韓 以捷(Yljle Han)
群再大 工 五十嵐 善英(Yoshihide Igarash1) Kentucky大Miroslaw Truszczynskl
tally 集合上のP 一置換群の代数的構造について 155
東電機大 理工 西野 哲朗(Tetsuro Nishino)
On Polynomial Time Many-One Completeness of One-Way Functions 162 東工大 工 渡辺 冶(Osamu Watanabe)
電通大 戸田 誠之助(Se mosuke Toda)
Topolo91cal Sortlngの NLOG 完全性について 169
九大理 正代隆義(Takayosh1 Shouda1)
PeLYNOMIAL-TIME ACCESSIBILITY TO SYMMETRIC SOLUTIONS 178
立教大理 山上智幸(Tomoyuk1 Yamakami)
安全な One 一一 way Functlon について 188
電通大 陳 致中(Chen Zh1-Zhong) 電通大 笠井 琢美(Takumi Kasa1)
確率的多項式時間アルゴリズムの能力について 198 電通大 戸田 誠之助(Selnosuke Toda)
一一111一
23一人ケームH1-Qについて
電通大
東海大 計算セ 24 耐故障ネノトワークと辺付加問題
広大 工 広大 工 広大 工 25 動的な占に対するVoronOl図について
九工大 情報セ 26
ヒクチャ ハターノ昭合アルゴリズム
九大 理工
27
自動検証について
阪大 基礎工 阪大 基礎工
28
Using Regular Temporal Logic 京大 工 京大 工 京大 工
29
三重大 工 三重大 工
原田辺村井田上岩渡東中今竹
隆平(Ryuhel Uehara) 茂樹(Shlgekl Iwata)
敏正(Toshlmasa Watanabe) 靖彦(Yasuhlko Hlgash1) 昭(Akira Nakamura)
桂子(Kelko Ima1)
正幸(Masayuki Takeda)
整数線形計画問題の解非存在性判定を利用した通信プロトコルの
東野 輝夫(Teruo Higashlno) 谷口 健一(Ken, ichi Tanlguch1¿
On Design Verification between Different Levels of Abstraction
濱口 清冶(Klyoharu Hamaguch1) 平石 裕実(Hlroml Hiralshi) 矢島 脩三(Shuzo YaJlma)
非同期通信に基づく並列処理言語の表示的意味記述について
那須 隆(Takashl Nasu)
大山口 通夫(Mlchlo Oyamaguch1)
205
215
225
233
243
253
263
噛1Ψ一
30 VLSIレイアウト設計におけるフ・ロノク配置の改良 広大 工 大村 広大 工 宮尾 広大 工 若林
道良B(Mlchlroh Ohmura)
淳一一(Jun,1chl Mlyao) 真一(Shln 1chl Wakabayash1)
273
一v一
