Voltar
Artigo Revisado por pares
BIBTEX RIS

Maze recognizing automata and nondeterministic tape complexity

1973; Elsevier BV; Volume: 7; Issue: 4 Linguagem: Inglês

10.1016/s0022-0000(73)80031-5

ISSN

1090-2724

Autores

Walter J. Savitch,

Tópico(s)

Computability, Logic, AI Algorithms

Resumo

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)≥log2n.

Referência(s)