文献

J-GLOBAL ID：201602004980862820   整理番号：71A0258569

多ヘッドと補助スタックオートマトンによるチューリング機械のあるテープと時間複雑さのクラスの特性化

Characterizations of some tape and time complexity classes of turing machines in terms of multihead and auxiliary stack automata.

著者 (1件)： IBARRAO H
資料名： J Comput Syst Sci  (Journal of Computer and System Sciences)
巻： 5  号： 2  ページ： 88-117  発行年： 1971年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： チューリング機械のテープと時間複雑さのクラスを閉じたクラスとして記述するモデルを見つけ,それの計算能力を求める。そのためkヘッドスタックオートマトン(k-SA)と補助スタックオートマト、を導入し.その無限記憶を取扱う仕方によっていくつかのタィブを定義する。このとき、これらのオートマトンの計算能力に関すろ結果を与える。例えば,集合がk-SAで管理されることと,それがこのcn^2k乗-時間バウンデッドな決定性チューリング機械で受理されたることは等価である。この他,数多くの結果を与える;表3参12

シソーラス用語： Turing機械 ,  スタックオートマトン ,  計算の複雑さ ,  計算理論

タイトルに関連する用語 (6件)： スタックオートマトン ,  チューリング機械 ,  テープ ,  複雑さ ,  クラス ,  特性化