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 recogni
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).
show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Author:Juraj Hromkovič, Georg Schnitger
URN:urn:nbn:de:hebis:30-75593
Document Type:Conference Proceeding
Language:English
Date of Publication (online):2010/03/09
Year of first Publication:2009
Publishing Institution:Univ.-Bibliothek Frankfurt am Main
Release Date:2010/03/09
Tag:ambiguity ; communication complexity; nondeterministic finite automata
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
Dewey Decimal Classification:004 Datenverarbeitung; Informatik
Sammlungen:Universitätspublikationen
Licence (German):License Logo Veröffentlichungsvertrag für Publikationen

$Rev: 11761 $