時間と葉の数を限定した1テープオルタネーティングチューリング機械

山本 博章  野口 正一  

誌名
電子情報通信学会論文誌 D   Vol.J68-D   No.10   pp.1719-1726
発行日: 1985/10/25
Online ISSN: 
DOI: 
Print ISSN: 0913-5713
論文種別: 論文
専門分野: オートマトン・言語理論
キーワード: 


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


あらまし: 
本論文では,1テープTuring machine(TM,非決定性または決定性)における通過列を1テープATM(alternating Turing machine)へ拡張し,それによって次の結果を得る.
(1) 時間,葉が同時にそれぞれOTn)),OBn))に限定された1テープATMはATMによって時間O((TnBn))1/2)で模倣される.
(2) fnn-1)/2なる関数fn)に対し,L={xyxxyx|=nx{0,1}*y{2},|x|=fn)}としたとき,もしLが1テープATMにより時間Tn)かつ葉Bn)で受理されるならば,そのとき,supn→∞TnBn)/nfn)>0.