時間,葉,領域限定ATMとリバーサル,領域限定NTMとの関係

山本 博章  野口 正一  

誌名
電子情報通信学会論文誌 D   Vol.J67-D   No.8   pp.845-852
発行日: 1984/08/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: 
キーワード: 


本文: PDF(711.4KB)
>>論文を購入


あらまし: 
いくつかの決定性の並列計算のモデルに対し,その時間とプロセッサ数間のトレードオフや各モデル間の関係などが調べられているが,非決定性を許した場合に関してはあまり調べられていない.本論文では,非決定性を許した場合に関する考察をATM(Alternating Turing Machine)とNTM(Nondeterministic Turing Machine)を用いて行なう.主な結果は,(1)Rn)=OSn)),Rn)=Ω(log(Sn)),Sn)=Ωn)のとき,NRS1R0(1)n),S0(1)n))⊆ATBS(R0(1)n),S0(1)n),R0(1)n))⊆NRS(R0(1)n),S0(1)n),S0(1)n)),(2)Sn)=ORn)),Sn)=Ω(log(Rn)),Rn)=Ωn)のとき,NRS(R0(1)n),S0(1)n))=ATBS(R0(1)n),S0(1)n)).ここで,NRS(Rn),Sn))(ATBS(Tn),Bn),Sn)))は〔Rn),Sn)〕リバーサル,領域限定NTM(〔Tn),Bn),Sn)〕時間,葉,領域限定ATM)によって受理される言語のクラス.