オンライン多テープチューリング機械のε-動作に関する一考察
スポンサーリンク
概要
- 論文の詳細を見る
Let f (n) be a time function. By k-DTM (f (n)) (k-NTM (f (n))), we denote the class of languages accepted by deterministic (nondeterministic) on-line k-tape Turing machines which, given an input of length n, operate in such a way that the input heads stay on the same input position at most f (n) steps. This paper shows that if lim [f (n)/(log n)^r]=0 for some positive constant r, then (1) [numerical formula] and [numerical formula], and (2) [numerical formula] and [numerical formula] are not closed under concatenation, Kleene closure, length-preserving homomorphism, or reversal.
著者
関連論文
- パーソナルコンピュータ PET 2001-8 への高速カセットテープレコーダ MT-2 のインターフェース
- メッシュ配列並列計算機の耐故障化のための再構成に関する1考察 : 危険なプロセッサ数の最小化
- 単一トラック切換網を持つメッシュ結合アレーのニューラルネット解法による再構成
- NOAA衛星画像との比較による気象衛星「風雲」赤外APT画像の温度変換
- 静止気象衛星GMS,WEFAX受信パラボラアンテナ用一次放射器
- 気象衛星メテオール画像の歪補正
- 気象衛星NOAA-APT受信空中線
- 気象衛星メテオ-ル画像の歪補正
- 気象衛星ノアAPT画像の球面幾何歪補正
- 無線印刷電信気象通報解読の研究 : 高層気象現況図作図プログラムの開発
- コオペレーティング1方向カウンタ機械システム
- Optimal Simulation of Two-Dimensional Alternating Finite Automata by Three-Way Nondeterministic Turing Machines
- Some Hierarchy Results of Alternating Automata with Counters and Stack-Counters
- A Hierarchy Result of Cooperating Systems of Two-Way Counter Machines
- ある制限を加えた同期型交代マルチヘッド有限オートマトン
- 再構成によるトリー状結合高並列計算機の高信頼化とその信頼性解析
- メッシュ配列並列計算機の耐故障化のための再構成に関する1考察 : 危険なプロセッサ数の最小化
- 単一トラック切換網を持つメッシュ結合アレーのニューラルネット解法による再構成
- マーカをもつマルチヘッド有限オートマタ
- 実時間1方向オールタネイティングマルチスタックカウンタオートマタの階層性
- A note on one-way multicounter machines and cooperating systems of one-way finite automata
- ピラミッドアーキテクチャによる 4 分木データ構造表現の並列図形処理
- 1方向マルチプロセッサ有限オートマタのある性質
- コオペレーティング1方向有限オートマタシステムのある性質
- 格子状結合高並列計算機の高信頼化の一構成とその信頼性解析
- コオペレーティング1方向カウンタ機械システム(理論計算機科学とその周辺)
- A Relationship between nondeterministic Turing machines and 1-inkdot Turing machines with small space
- 3次元2値画像処理のための並列計算機
- AE による切削工具損傷監視制御システム(第 1 報)
- イテラティブアクセプタに関するある性質
- 同種シストリックピラミッドオ-トマタに関するある性質
- 消費税に対する「分割買い」について(アルゴリズムと計算量の理論)
- 多値論理関数を実現するセル配列の故障検査(多値論理及びその応用(4))
- M-AND, M-OR, NOT演算を用いた多値論理関数の簡単化に関する一考察(多値論理及びその応用(4))
- 多値論理関数を実現するセル配列の故障検査
- Voronoi diagram 構成のための並列アルゴリズム
- 2次元マーカオートマトンのある性質 : 3方向チューリング機械による模倣(計算アルゴリズムと計算量の基礎理論)
- 2スキャナ1次元限定セル構造アクセプタ
- マイコンによる音声認識システムと中国語の認識
- A Note on Three-Way Two-Dimensional Alternating Turing Machines
- 回転入力をもつ1次元限定セル構造アクセプタ--積形と和形の関係
- 回転入力をもつ1次元限定セル構造アクセプタ
- マイコンによる英文ワードプロセサー
- LISP における変数の結合方式について
- 近傍制限直並列アレイアクセプタ
- 非決定性シンプルマルチヘッドオ-トマタに関するある性質
- パス限定2次元マルチパスオンラインテセレ-ションアクセプタ
- パソコン APPLE II を用いた TSS 端末装置の製作
- 自己組織的に構成される逐次検索表とOpen Scatter Table (計算機構の数学的研究)
- 1次元限定セル構造アクセプタによる連結テ-プの認識について
- k近傍〓形2次元限定セル構造アクセプタの階層性
- k近傍〓形2次元限定セル構造アクセプタ
- A Note on Alternating On-Line Turing Machines (形式言語理論とオ-トマトン理論)
- 回転入力をもつ2次元オ-トマタ--積形と和形の関係
- 回転入カをもつ2次元オートマタ : 和形と積形の関係 (数理情報科学の基礎理論と応用)
- 3次元6方向有限オ-トマタと3次元5方向チュ-リング機械の受理能力の関係
- 回転入力をもつ2次元オ-トマタ--和形
- マイコンを用いたタブレットによる図形入力システムの製作
- 2 次元オンラインテセレーションアクセプタの AFM 性
- 回転入力をもつ2次元オ-トマタ(積形)
- 正方形テ-プ上で動作する各種の2次元オ-トマタの受理能力
- 準1方向シンプルマルチヘッド有限オ-トマタ
- 準3方向と3方向のシンプルマルチヘッド有限オートマタの関係 (情報科学の数学的基礎理論と応用)
- 3方向2次元シンプルマルチヘッド有限オ-トマタ--閉包性
- 3方向2次元シンプルマルチヘッド有限オ-トマタ--階層性
- マイコンを用いたデータ収集システム(その 1)
- パーソナルコンピュータ PET 2001-8 の拡張 : メモリ増設と P-ROM (2708 用) ライタのインターフェース
- PET 2001 用逆アセンブラー
- PET 2001 用ハードコピーシステム
- MCS-6502 マイクロコンピュータの逆アセンブラー
- MCS-6502 を CPU とするマイクロコンピュータシステム : 高速ドットプリンタ PA6651-A とのインタフェース
- 逐次検索における自己組織化ファイルの発見的構成
- オンライン多テープチューリング機械のε-動作に関する一考察
- テ-プ限定2次元チュ-リング機械で受理される集合族の閉包性に関するコメント(技術談話室)
- テ-プ限定2次元チュ-リング機械で受理される集合族の閉包性に関する一考察
- A Space Hierarchy Result of Two-Dimensional Alternating Turing Machines with Only Universal States(Mathematical Theories on Computing Schemes and Their Applications)
- 正方形テ-プ上で動作する3方向2次元マルチカウンタオ-トマタに関する二,三の性質
- A Note on Decision Problems for Three-Way Two-Dimensional Finite Automata (情報科学の数学的基礎理論と応用)
- 2次元テ-プ上のオ-トマタで受理される集合族の二つの演算に関する閉包性
- A Note on Algorithms for Tower of Hanoi (計算機科学の数学的基礎)