Relationships Between Nondeterministic and Deterministic Tape Complexities

Walter J. Savitch, 1970, Journal of Computer and System Sciences

About this paperEnglishTiếng Việt中文beside Englishbeside Tiếng Việtbeside 中文

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

非決定性テープ計算量と決定性テープ計算量の関係*

Walter J. Savitch

応用物理学・情報科学部門 カリフォルニア大学サンディエゴ校、ラホヤ、カリフォルニア州 92037

1969年8月29日受理

決定性チューリング機械上で非決定性テープ制限チューリング機械をシミュレートするために必要な記憶容量について考察する。結果には次のものが含まれる。定理。L(n)≥log⁡2nL(n) \geq \log_2 nであるとき、非決定性のL(n)L(n)-テープ制限チューリング機械は、決定性の[L(n)]2[L(n)]^2-テープ制限チューリング機械によってシミュレートできる。非決定性機械の計算は、ある種の迷路の通り抜けに対応することが示される。この対応を用いて、通り抜け可能な迷路のすべての符号化の集合という特定の集合を構成する。すなわち、非決定性テープ計算量クラスと決定性テープ計算量クラスを区別する集合が存在するならば、この集合もそのような集合の一つである。

References

  1. M. Blum, A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach. 14 (1967), 322–336.
  2. A. Cobham, “The Recognition Problem for the Set of Perfect Squares.” IEEE Conference Record of the Seventh Annual Symposium on Switching and Automata Theory, Berkeley, Calif., 1966, pp. 78–87.
  3. J. E. Hopcroft and J. D. Ullman, “Formal Languages and Their Relation to Automata.” Addison-Wesley, Reading, Mass., 1969.
  4. J. E. Hopcroft and J. D. Ullman, Relations between time and tape complexities. J. Assoc. Comput. Mach. 15 (1968), 414–427.
  5. S. Y. Kuroda, Classes of languages and linear-bound automata. Information and Control 7 (1964), 207–223. (The relevant material also appears in [3], pp. 115–119.)
  6. P. S. Landweber, Three theorems on phrase structure grammars of type 1. Information and Control 6 (1963), 131–136. (The relevant material also appears in [3], pp. 115–119.)
  7. P. M. Lewis II, R. E. Stearns, and J. Hartmanis, “Memory Bounds for the Recognition of Context-Free and Context-Sensitive Languages.” IEEE Conference Record on Switching Circuit Theory and Logical Design, Ann Arbor, Mich., 1965, pp. 191–202. (The relevant material also appears in [3], pp. 162–164.)
  8. E. M. McCreight and A. R. Meyer, “Classes of Computable Functions Defined by Bounds on Computation: Preliminary Report.” Conference Record of ACM Symposium on Theory of Computing, Marina del Rey, Calif., May 1969, pp. 79–88.
  9. W. J. Savitch, “Deterministic Simulation of Non-deterministic Turing Machines (Detailed Abstract). Conference Record of ACM Symposium on Theory of Computing, Marina del Rey, Calif., May 1969, pp. 247–248.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 日本語 by gpt-5, against glossary version 6. Translated from the English.