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).
Author: | Juraj Hromkovič, Georg Schnitger |
---|---|
URN: | urn:nbn:de:hebis:30-75593 |
Parent Title (German): | 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 |
Document Type: | Conference Proceeding |
Language: | English |
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 |
Note: | (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 ; http://www.stacs-conf.org |
HeBIS-PPN: | 221787887 |
Institutes: | Informatik und Mathematik / Informatik |
Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
Licence (German): | Creative Commons - Namensnennung-Keine kommerzielle Nutzung-Weitergabe unter gleichen Bedingungen |