This paper presents efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with ε-transitions. It gives an algorithm for testing the exponential ambiguity of an automaton A in time O(|A|_E~2), and finite or polynomial ambiguity in time O(|A|_E~3), where |A|_e denotes the number of transitions of A. These complexities significantly improve over the previous best complexities given for the same problem. Furthermore, the algorithms presented are simple and based on a general algorithm for the composition or intersection of automata. We also give an algorithm to determine in time O(|A|_E~3) the degree of polynomial ambiguity of a polynomially ambiguous automaton A. Finally, we present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton.
展开▼
机译：本文提出了一种有效的算法，用于测试具有ε跃迁的有限自动机的有限，多项式和指数歧义。它给出了一种算法，用于测试时间为O（| A | _E〜2）的自动机A的指数歧义，以及时间为O（| A | _E〜3）的有限或多项式歧义，其中| A | _e表示数字这些复杂性大大超过了以前针对同一问题给出的最佳复杂性。此外，提出的算法很简单，并且基于自动机的组成或交集的通用算法。我们还给出了一种确定时间O（| A | _E〜3）的多项式歧义自动机A的多项式歧义程度的算法。最后，我们介绍了我们的算法在概率自动机熵的近似计算中的应用。 。
展开▼
