LIPIcs.STACS.2009.1805.pdf
- Filesize: 186 kB
- 12 pages
Document
Ambiguity and Communication
Authors
-
Part of:
Volume:
26th International Symposium on Theoretical Aspects of Computer Science (STACS 2009)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2009-02-19
Cite As Get BibTex
Juraj Hromkovic and Georg Schnitger. Ambiguity and Communication. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 553-564, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
https://doi.org/10.4230/LIPIcs.STACS.2009.1805
Abstract
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).
Subject Classification
Keywords
- Nondeterministic finite automata
- Ambiguity
- Communication complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads