薮理解析研究戸

(1)

・一一 S;H/bYV} ,

薮理解析研究戸

心論

ng さ甑熊 1?

処理 5

数理解析研究所講究録 494

(

計算機構に関する数学的基礎理論とその応用

禁帯出期間

58e 7e 27 m 一 8 ・一 3

A

数研図書室

京都大学数理解析研究所

1983

年

6

月

ノ

a

(2)

R:IYIS Kohy”2tofeu 494

silii 2iiK ]7k¡,. iiiili!i2

84056707

pa $

Xieefi47M-EfflilZEjr

Mathematical Theories on Computing

and

Their App1ications

Schemes

June, 1983

Research Institute for Plathematical Sciences

Kyoto University, Kyoto, Japan

(3)

l.

2.

3.

t;-)r IIIil ue 1& t: 2g6 G & -IIszL SII3 fa9 li!lin11ig { li! i-fa u1 di /4ilt; EA mgkftskezk

l983 th 2 F} lH- 2 fl 3H

/EiI’

}

IE6‘”vNlill/2jil5 ‘i ki 4ilEl’ i’ii;(shuzo yajima)

g z¡

1gllM V’51i’ jiill’ t: S& 5”’- 9 7ma ’1‘IIL · di 6K va · · · - · · e · e · · · · e · · · · e · · · i

d]1’rJt¡ [- .LMK { iilKE(yahiko Kambayashi) ip7)¡k 2B2liE e9vV MZs(Katsumi Tanaka)

Minimum Delay Semijoin Schedules for Loeal Area Distributed

Database Systems ..··e··e···..····e···.e·ee··ee·e· 13

2zJx. z VetlA glil (shigeru Masuyama)

llig ll5Ea‘A7ilS(shojiro Muro) i!iZ7K 6{itas(Toshihide Ibayaki)

7k.G’ 21E (Tadashi Mizutani)

ke))l jPl ’.‘ttS(Toshiharu Hasegawa)

gfi4k,, { r”-gA”N-7z. { ;asstk 3iS.2Ii (.’i:[ jillil S(tz · IEg! o) deX4 } c, tc7b Z . . . , . 2s

jEiZ, k. J lll

}

ll jE612t(Masatoshi yoshikawa)

”t- ijk gS¡Ei (yahiko Kambayashi) 5¡2k 6Li { C;’ (shuzo yajima)

-i-

(4)

r

4.

ノ分取形デレタペース、における単秦屯田合・せ

e

の巖適イヒ

,t:

二つし

1

て。

.

。。

..

。

.35

広大エ膨壕一夫 (Kazu・Sugihara) 宮尾瘍!(Jun ichi Miya・) 菊野盲 (T・hru Kikun・)

5. REMARKS ON REA:L・一TIME DETERMIN工STIC CONTEXT-FREE LANGUAGES ...。.。 46

二刀エ封嵐善英 (Y・shihide エ garashi)

6. Characte:rization of ω一Regular I・anguages by Firs七・一〇]Pder

Formulas ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・… 58

東エ大理ノ1・塊茎7欠郎(K。」ir・K・bayashi) 高縮正:}(Masak・Takahashi) 山爾禿記(Hideki Yamasaki)

7. A CONSTRUCT工ON O:F THE NERODE EQU工VA:LENCE工N C:LOSED

CATEGOR工ES 。・… 。・。・・。・・・・・・…9…9・… 。・・。・一・…,・…70

77.tx 理列壕廉雄 (Yasu・Kawahara)

8.

ある種の代数的シスラムに付確し誘ゐ無予艮竹列のノ性

,

後

....

。

....

。

78

山梨大工内お粧輔

(Keisuke Uchimura) 9.

甚本操作の依有性乞利用した並行処理のための手法. ...90

怠丸工逝 L藤:訪{}˜ 一(Seiichi Kondo)

上林弥彦(Yahik・Kambayashi) 矢島イ

1

旨三

(Shuz

・

Ya

」

ima)

の

一ユユ一・

(5)

IO.

ll.

ユ2.

13・

14.

Serializable Classes の楢痘につし、て.. .. .. ..102 京丸エ幻出油類丁。shihideエbaraki) ウ托ンフレD・一・X亀田恒彦(Tsunehik・Kameda) れゴ・ン†肱大箕ラ甫敏美

(T

・

shimi Min

・

ura)

分散型シスラムにおける粗互排除のためのトークンを用いたスキームにフい

Z

e-eeeeeeee-eeeeeeeeeeeeeee L14 京大エ室章冶郎(Sh。」ir。 Mur。)

神ア商科大加藤直樹(Na・ki Kat。h) れゴン、

11

畝箕禰敏美

(T

・

shimi Min

・

ura)

京大工長谷) 1利冶 (i]i・shiharu Hasegawa) Transformations of Communicating Sequential Processes... 126

ム梨大エ客舎広陵(Hir・yuki Musha) 徳田雄拝(Takehir・T・kuda)

デ、うタル義・何労

1

二あ・ける図形とその

COmputational Complexity

{ ^{こついて・}^・^{・… 。}^{・… 。}^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・^・… 137

広 k エキ村昭 (Akira Nakamura) 会詠手蘇一(Kuni・Aizawa)

Gradually lntractable Problems … .・・・・・・・・… .・・… .・・ 148

電画太笠面諭美 (Takumi Kasai) 東知尺岩田茂樹 (Shigeki エ wata)

一].ユ].一一

(6)

15・

16.

17・

18.

19e

20.

The Relation between Time and Accepting Probability on Probabilistic Simple Decision Trees .。...,.... 160

東エK理渡辺;m4(Osamu Watanabe)

A Space Hierarchy Result of Two・一Dimensional A1七ernating Turing Machines with Only Universal States ....。...・・ 172

山ロ大エ A; 克司 (Katsushi エn・ue) 俘藤晩(Akiraエt・) 高這:五男(ltSU・Takanami)

二三弘(Hir・shi Taniguchi)

Time-optimum para1:Le]一binary add:ress se七ting algorithms for a:rray processO:rs ・・… 。… 。・・・・・・・・・・・・・・・… 。・・… 185

阪電直夫エ旛尾傳司(Hir・shi Ume・)

多オートマトン

k

の進化

. . . .

、

g4

京た理面尾英之 Ek(Hiden・suke Nishi・) 青藤隆(Takashi Sait・)

フ On グラムの検証と完備な述 1 「語のクラス ... 。 ... 。 ...203

名穴山尉」b 昌乙 (Masami Murakami)

稲垣康善

(Yasuy

。

shi

・

nagaki)

豊橋山斗犬」zli,・・多殻雄(Nami。 H・nda)

正規

:

論理

.

とその

model

にフいて

... ..6.,.... .215

kUKコ〉窃一舛乏術閑発機描坂お広(K・Sakai)

一 ■V一

(7)

21.

22.

23·

24.

Hardware Algorithms for Division and Square Rooting

Internally Using Redundant Binary Representation ..,.. 223

SRK ; aJt. iESRL (Naofumi Takagi) Ti;ilaN gl,/k. (Hiroto yasuura) Sii.k 5iili-!i;- (Shuzo yajima)

VL S I E- ii ’”) L·”N U) 7””ii’ ’7 ¡i’¿ 1Ie. (V) SL2)¿. (}) t :, ” ” ’lr e· · ·e e e· · · ·e e· ·236

igig). k. ¿E’M Sst;? l;Hl (seinosuke Toda) lt.e,T3l IEig(.;E¡(Takumi Kasai)

jE a}l izi SfiiiEljIL n{!21}kzg’S e Iillil2-)a Zl) ’i}fil ciigl}a Si}li’(D ?E.##; iS . . , . . . , 248

”M- X - tr}M’ ergz/¡..(Hiroto yasuura) i¿ikjllb 6iiEt:’ (shuzo yajima)

ilE ffi. gllL4I;h 2 ifl ”iigl 6 Zi? A09– 7 ’7Ny ’5’ i/ 7‘ ’ 7}/ ;/ e e· · · ·e· · · e·259

?diX ; E17k a-(shin’ichi wakabayashi) ffiit # k !=yiN ( [v aka shi Fuj i i)

gfi 9? 1? ([pohru Kikuno)

-v-

薮理解析研究戸