Ambiguity and Communication

2009/02/12 by Juraj Hromkovic, Georg Schnitger · 1 voice · 1 citation
Computer Science · #cs.CC #cs.FL

paper · pdf

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

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

Cited by

• A simple algorithmic framework for disambiguation of finite automata

Discussions

• OK, determining if a NFA is ambiguous (aka "can I parse this string constructed with concatenation more than one way?") is tougher than I thought it would be. I also know I'm starting to get in over m [bsky, 0 points, 0 comments]

Related

• Polynomially Ambiguous Probabilistic Automata on Restricted Languages
• General Algorithms for Testing the Ambiguity of Finite Automata
• Fined-Grained Complexity of Ambiguity Problems on Automata and Directed Graphs
• Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata
• Lengths of Words Accepted by Nondeterministic Finite Automata