Ambiguity and communication

  • The 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).

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Author:Juraj Hromkovič, Georg Schnitger
Parent Title (German):26th International Symposium on Theoretical Aspects of Computer Science STACS 2009
Document Type:Conference Proceeding
Year of Completion:2009
Year of first Publication:2009
Publishing Institution:Universitätsbibliothek Johann Christian Senckenberg
Release Date:2010/03/09
Tag:ambiguity; communication complexity; nondeterministic finite automata
First Page:553
Last Page:564
(c) J. Hromkovic and G. Schnitger ; Creative Commons Attribution-NoDerivs License
Source:26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 553-564 ;
Institutes:Informatik und Mathematik / Informatik
Dewey Decimal Classification:0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik
Licence (German):License LogoCreative Commons - Namensnennung-Keine kommerzielle Nutzung-Weitergabe unter gleichen Bedingungen