文献

J-GLOBAL ID：201602005634824420   整理番号：72A0268309

多ヘッド有限オートマトンによる計算

Computation by multi-head finite automata.

著者 (1件)： SUDBOROUGH I H
資料名： IEEE Conf Rec Annu Symp S  (IEEE Conference Record of Annual Symposium on Switching and Automata Theory)
巻： 1971  ページ： 105-113  発行年： 1971年 
JST資料番号： D0710A  CODEN： ICSAB   資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： nヘッド書き込み有限オートマトン(n-wfa)は一本の入カテープ上にn個の一方向読み書きヘッドをもつ有限状態機械である。n-wfaが認識する言語の族(W_n)と他のモデル(nヘッド書き込みなし有限オートマトン.線形有界オートマトン.実時間バッファオートマトンなど)が認識する言語との関係.2-wfaと1テープオフラインチューリング機械の計算の複雑さのクラス間の関係を与える。これを用いて.W₂とプッシュダウンオートマトン,nヘッドプッシュダウンオートマトンなどが認識する言語の族は比較できないことを示す;参8

シソーラス用語： オートマトン理論 ,  計算の複雑さ ,  有限オートマトン

タイトルに関連する用語 (2件)： 有限オートマトン ,  計算