アルゴリズムと計算量の理論

一幻 0 乙 )2

数理解析研究所講究録 731

アルゴリズムと計算量の理論

京都大学数理解析研究所

1990 年 10 月

ノ

Zo

1

3

4

5

6

5

アルゴリズムと計算量の理論 研究集会報告集

1990年2月1日{}2˜ 月3日

研究代表者 小林 孝次郎(KoJlro Kobayash1)

目 次

ねヘ シ

ノ禽欝轡策

、 1 _{∴∵ 鵠}

キロ轟 ラ綿

} ^{〆…キロ幽}

ボ ドぼ

繍鰹 。擁ご〆沸

Cut free systems for some tense logics

東工大 理 鹿島 亮(Ryo Kashima)

A new head-normalization algonthm for A-calculus

東工大 理 野口 審一(Ken-1chi Noguchl)

tontluence dnd Completion ot Membership Conditional TRS

NTT基礎研 山田 順之介(Junnosuke Yamada)

高階ユニフィケーノヨノにおける可解なクラスと計算の複雑さ

九工大 情報工 二二 政輝(Masateru Harao) 山形大 工 岩沼 宏冶(KouJl Iwanuma¿

OcLam Algorithms for Learning from Noisy Exdmples

富士通 榊原 康文(Yasubumi Sakaklbara) Learning Equal Matrix Grammars and Multitape Automata with

Structural lnformation

富士通 高田 裕志(YUJl Takada)

。吾彙機能文法と計算量

東電機大 理工 西野 哲朗(Tetsuro Nlshlno) A learning algorithm for monotone rc一term DNF

東北大 工 大里 毅(Takesh10hguro)

〃 丸岡 章(Aklra Maruoka)

1

3

ユ

25

37

49

61

7?

84

1

9

∩ U- _⊥ - _北 - _置⊥

!2

3 1

14

15

決定的に構文解析かてきる

2

国立民族学博物館 山本 泰則(Yasunorl Yamamoto) 山形大 工 森田 憲一(Kenlchl Morlta)

1

2

山形大 工 森田 憲一(Kenlchl Morlta) 一方向マルチフロセノサ有限オートマタのある性質

山口大工 角川裕次(Hlrotsugu Kakugawa) 大島商船高專 松野 浩嗣(Hlroshl Matsuno)

山口大 工 井上 克司(Katsushl Inoue)

〃 高浪 五男(Itsuo Takanam1) Closure properties of (v-languages under morphism and

inverse morphism

国士館大 情科セ 守谷 哲夫(Tetsuo Morlya) 高々スター次

:

n

豊橋技科大 劉 僖根(Heekeun Yoo)

〃 橋口 攻三郎(Kosaburo Hashlguch1) 消費税に対する「分割買い」について

山口大 工短 伊藤 暁(Aklra Ito) 山口大 工 井上 克司(Katsushl Inoue)

〃 高浪 五男(Itsuo Takanam1)

Lexicographically optimal base of a submodular system with respect

to a weight vector

城西大 理 岩村 覚三(Kakuzo Iwamura)

97

108

1!8

130

143

155

166

6 1

7

!

8

!

1 9

∩ U- _{⊥り乙り乙}

凸多角形の多角形領域内へのmaxlmln配置問題とそれに関連した 動的

Vorono1

九大 工 青沼 裕美(Hlroml Aonuma) 九大 工 今井 浩(Hlroshl Ima1) 九工大 情報セ 今井 桂子(Kelko Ima1) 日本IBM東京基礎研 徳山豪(Takeshl Tokuyama) 内占法の平面

n

九大 工 今井 浩(Hlroshl Imai)

〃 田川 二二(YUJI Tagawa) On the Laigest Common Subgraph Problem

豊橋技科大 増山 繁(Shlgeru Masuyama)

〃 高橋 由雅(Yoshlmasa Takahash1)

〃 奥山 f散(Tohru Okuyama)

〃 佐々木慎一(Shln-ichl Sasak1)

k

k

豊橋技科大 二二 仁(Hltoshi Nagamochi¿

京大 工 茨木 俊秀(Toshihlde Ibarak1)

A New Series of AP2-Cornplete Problems

九大 理 宮野 悟(Satoru Mlyano)

Grammatical Characterizations of P and PSPACE

g 電通大 陳 致中 (Zh1-Zhong Chen) 電通大 戸田 誠之助(Selnosuke Toda)

177

187

195

202

214

226

111

22 Three Criteria for Selecting Variables in the Construction of Near-Optimal Decision Trees

電総研 宮川 正弘(Masahlro臨yakawa)

〃 大津 展之(Nobuyuk10tsu)

23 :

九大 大型セ 古川 哲也(Tetsuya Furukawa) 九大 工 上林 彌彦(Yahlko Kambayashi) d4 Towards Temporal ebJect-Oriented Databases

九大 工 Mohamed El-Sharkawi

〃 上林 彌彦(Yahlko Kambayashi)

25

九大 工 岩井原 瑞穂(Mizuho Iwaihara)

〃 上林 彌彦(Yahlko Kambayash1)

2b リノク構造における検索処理効率と更新処理効率の関係について

九大 工 木前 新一(Shmlchl Konomi) 九大 大型セ 古川 哲也(Tetsuya Furukawa)

九大 工 上林 彌彦(Yahlko Kambayash1)

238

250

262

274

286