Ambiguity and Communication

Simple item page
dc.creatorHromkovic, Juraj
dc.creatorSchnitger, Georg
dc.date2009-02-12
dc.date.accessioned2026-07-07T12:47:29Z
dc.date.available2026-07-07T12:47:29Z
dc.descriptionThe ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for an input of size n. For all k, r 2 N we construct languages Lr,k which can be recognized by NFA's with size k poly(r) and ambiguity O(nk), but Lr,k has only NFA's with exponential size, if ambiguity o(nk) is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, 1989, Leung, 1998).
dc.identifierhttps://arxiv.org/abs/0902.2140
dc.identifierhttp://arxiv.org/abs/0902.2140
dc.identifier26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 553-564
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/221735
dc.subjectFormal Languages and Automata Theory
dc.subjectComputational Complexity
dc.titleAmbiguity and Communication
dc.typetext

Files

Collections

arXiv