Ambiguity and Communication

Details Ambiguity and Communication Ambiguity and Communication

2009-02-12

arxiv.org/abs/0902.2140v1

26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 553-564

Computer Science

Formal Languages and Automata Theory

Scientific paper

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).

Affiliated with

Also associated with

No associations

Rating

Ambiguity and Communication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ambiguity and Communication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ambiguity and Communication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-556703