実時間1方向オールタネイティングマルチスタックカウンタオートマタの階層性

概要

論文の詳細を見る
実時間で動作する1方向オールタネイティングマルチスタックカウンタオートマタ(1amsca's)及び1方向オールタネイティングマルチカウンタオートマタ(1amca's)の受理能力について考察している.各k≧1に対し,実時間1方向オールタネイティングk-スタックカウンタ(k-カウンタ)オートマタにより受理される集合の族を1ASCA(k,real)(1ACA(k,real))と記し,また,全称状態だけからなる実時間1方向オールタネイティングk-スタックカウンタ(k-カウンタ)オートマタにより受理される集合の族を1USCA(k,real)(1UCA(k,real))と記す.初めに,実時間1amsca's(1amca's),全称状態だけからなる実時間1amsca's(1amca's),及び,存在状態だけからなる実時間1amsca's (1amca's)の受理能力の関係について考察する.次に,カウンタ及びスタックカウンタの数に基く階層性について考察し,例えば,各k≧1に対し,1USCA(k+1,real)-1ASCA(k,real)≠φ,1UCA(k+1,real)-1ACA(k,real)≠φを示す.最後に,実時間1amsca'sと実時間1amca'sの関係について考察し,例えば,1USCA(i,real)=1UCA(j,real)をみたすi,jは存在しないこと及び,各k≧1に対し,1USCA(k,real)-1ACA(k,real)≠φを示す.
社団法人電子情報通信学会の論文
1993-09-24