TY  - CONF
A1  - Hromkovič, Juraj
A1  - Schnitger, Georg
T1  - Ambiguity and communication
T2  - 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009
N2  - 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).
KW  - nondeterministic finite automata
KW  - ambiguity
KW  - communication complexity
Y1  - 2009
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7580
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-75593
N1  - (c) J. Hromkovic and G. Schnitger ; Creative Commons Attribution-NoDerivs License
SP  - 553
EP  - 564
ER  -