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 |
