Making nondeterminism unambiguous

Authors
Reinhardt, K Allender, E
Citation
K. Reinhardt et E. Allender, Making nondeterminism unambiguous, SIAM J COMP, 29(4), 2000, pp. 1118-1131
Citations number
43
Categorie Soggetti
Computer Science & Engineering
Journal title
SIAM JOURNAL ON COMPUTING
ISSN journal
00975397 → ACNP
Volume
29
Issue
4
Year of publication
2000
Pages
1118 - 1131
Database
ISI
SICI code
0097-5397(20000306)29:4<1118:MNU>2.0.ZU;2-L
Abstract
We show that in the context of nonuniform complexity, nondeterministic loga rithmic space bounded computation can be made unambiguous. An analogous res ult holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as [GRAPHICS]