✦ LIBER ✦

Maze recognizing automata and nondeterministic tape complexity

✍ Scribed by Walter J. Savitch

Publisher: Elsevier Science
Year: 1973
Tongue: English
Weight: 682 KB
Volume: 7
Category: Article
ISSN: 0022-0000
DOI: 10.1016/s0022-0000(73)80031-5

No coin nor oath required. For personal study only.

✦ Synopsis

A new device called a maze recognizing automaton is introduced. The following two statements are shown to be equivalent. (i) There is a maze recognizing automaton that accepts precisely the threadable mazes. (ii) Every nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic L(n)-tape bounded Turing machine, provided L(n) > log2 n.

📜 SIMILAR VOLUMES

Relationships between nondeterministic a

Relationships between nondeterministic and deterministic tape complexities

✍ Walter J. Savitch 📂 Article 📅 1970 🏛 Elsevier Science 🌐 English ⚖ 816 KB

The amount of storage needed to simulate a nondeterministic tape bounded Turing machine on a deterministic Turing machine is investigated. Results include the following: Theorem. A nondeterministic L(n)-tape bounded Turing machine can be simulated by a deterministic [L(n)]2-tape bounded Turing machi

On tape-bounded complexity classes and m

On tape-bounded complexity classes and multihead finite automata

✍ I.H. Sudborough 📂 Article 📅 1975 🏛 Elsevier Science 🌐 English ⚖ 798 KB

The principal result described in this paper is the equivalence of the following statements : (1) Every set accepted by a nondeterministic one-way two-head finite automaton can be accepted by a deterministic two-way k-head finite automaton, for some k. (2) The context-free language Lp (described i