Making nondeterminism unambiguous

Klaus Reinhardt, Eric Allender

Research output: Contribution to journalArticlepeer-review

63 Scopus citations

Abstract

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
Volume29
Issue number4
DOIs
StatePublished - 2000

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

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

Cite this