2008/02/22 by Cyril Allauzen, Mehryar Mohri, Allauzen, Cyril +3
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Formal Methods in Verification #Machine Learning and Algorithms #cs.CC #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0802.3254
arxiv created 2008/02/22 · openalex publication_date 2008/02/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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|E2), and finite or polynomial ambiguity in time O(|A|E3). These complexities significantly improve over the previous best complexities given for the same problem. Furthermore, the algorithms presented are simple and are based on a general algorithm for the composition or intersection of automata. We also give an algorithm to determine the degree of polynomial ambiguity of a finite automaton A that is polynomially ambiguous in time O(|A|E3). Finally, we present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton.