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 |
| Document Type: | Conference Proceeding |
| Language: | English |
| Date of Publication (online): | 09.03.2010 |
| Year of first Publication: | 2009 |
| Publishing Institution: | Univ.-Bibliothek Frankfurt am Main |
| Tag: | ambiguity ; communication complexity; nondeterministic finite automata |
| 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 |
| Dewey Decimal Classification: | 004 Datenverarbeitung; Informatik |
| Sammlungen: | Universitätspublikationen |
| Note: | (c) J. Hromkovic and G. Schnitger ; Creative Commons Attribution-NoDerivs License |
| Licence (German): |  Veröffentlichungsvertrag für Publikationen ohne Print on Demand |
