2026-07-26T16:59:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1805 2024-03-06T10:33:13Z ddc:004 open_access

Ambiguity and Communication Hromkovic, Juraj Schnitger, Georg Nondeterministic finite automata Ambiguity Communication complexity 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 \in \mathbb{N}$ we construct languages $L_{r,k}$ which can be recognized by NFA's with size $k \cdot$poly$(r)$ and ambiguity $O(n^k)$, but $L_{r,k}$ has only NFA's with exponential size, if ambiguity $o(n^k)$ is required. In particular, a hierarchy for polynomial ambiguity is obtained, solving a long standing open problem (Ravikumar and Ibarra, 1989, Leung, 1998). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Juraj Hromkovic and Georg Schnitger 2009 Is Part Of LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2009.1805 urn:nbn:de:0030-drops-18054 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1805 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode