科研之友
微信
新浪微博
Facebook
分享链接
摘要
The ambiguity of a nondeterministic finite automaton (NFA) N for input size n is the maximal number of accepting computations of N for inputs of size n. For every natural number k we construct a family (L(r)(k) vertical bar r is an element of N) of languages which can be recognized by NFA's with size k.poly(r) and ambiguity O(n(k)), but L(r)(k) has only NFA's with size exponential in r, 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, SIAM J. Comput. 19: 1263-1282, 1989, Leung, SIAM J. Comput. 27: 1073-1082, 1998).
- 出版日期2011-4
