General Algorithms for Testing the Ambiguity of Finite Automata

Details General Algorithms for Testing the Ambiguity of Finite Automata General Algorithms for Testing the Ambiguity of Finite Automata

2008-02-22

arxiv.org/abs/0802.3254v1

Computer Science

Computational Complexity

Scientific paper

This paper presents efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with $\epsilon$-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)$. 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|_E^3)$. Finally, we present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton.

Affiliated with

Also associated with

No associations

Rating

General Algorithms for Testing the Ambiguity of Finite Automata 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 General Algorithms for Testing the Ambiguity of Finite Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and General Algorithms for Testing the Ambiguity of Finite Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-303118