Making nondeterminism unambiguous

Klaus Reinhardt, Eric Allender

Research output: Contribution to journalArticlepeer-review

63 Scopus citations


We show that in the context of nonuniform complexity, nondeterministic logarithmic space bounded computation can be made unambiguous. An analogous result holds for the class of problems reducible to context-free languages. In terms of complexity classes, this can be stated as NL/poly = UL/poly, LogCFL/poly = UAuxPDA(log n, nO(1))/poly.

Original languageEnglish (US)
Pages (from-to)1118-1131
Number of pages14
JournalSIAM Journal on Computing
Issue number4
StatePublished - 2000

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)


Dive into the research topics of 'Making nondeterminism unambiguous'. Together they form a unique fingerprint.

Cite this