𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On determinism versus nondeterminism for restarting automata

✍ Scribed by Hartmut Messerschmidt; Friedrich Otto

Book ID
113641765
Publisher
Elsevier Science
Year
2008
Tongue
English
Weight
273 KB
Volume
206
Category
Article
ISSN
0890-5401

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Determinism versus Nondeterminism for Li
Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions
✍ MiklΓ³s Ajtai πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 317 KB

Our computational model is a random access machine with n read only input registers each containing c log n bits of information and a read and write memory. We measure the time by the number of accesses to the input registers. We show that for all k there is an e > 0 so that if n is sufficiently lar

Guess-and-verify versus unrestricted non
Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines
✍ Martin Sauerhoff πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 258 KB

It is well known that a nondeterministic Turing machine can be simulated in polynomial time by a so-called guess-and-verify machine. It is an open question whether an analogous simulation exists in the context of space-bounded computation. In this paper, a negative answer to this question is given f

[IEEE Communication Technologies, Resear
[IEEE Communication Technologies, Research, Innovation, and Vision for the Future (RIVF) - Hanoi, Vietnam (2010.11.1-2010.11.4)] 2010 IEEE RIVF International Conference on Computing & Communication Technologies, Research, Innovation, and Vision for the Future (RIVF) - Determining Restricted Damerau-Levenshtein Edit-Distance of Two Languages by Extended Automata
✍ Dang, Quyet Thang; Phan, Trung Huy πŸ“‚ Article πŸ“… 2010 πŸ› IEEE βš– 165 KB