Paper Info
Title
General Algorithms for Testing the Ambiguity of Finite Automata
Abstract
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 Ain time $O(|A|_E^2)$, and finite or polynomial ambiguity in time $O(|A|_E^3)$, where |A|Edenotes 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.
Year
DOI
Venue
2008
10.1007/978-3-540-85780-8_8
Clinical Orthopaedics and Related Research
Keywords
DocType
Volume
finite automaton,polynomial ambiguity,previous best complexity,approximate computation,general algorithm,exponential ambiguity,general algorithms,finite automata,probabilistic automaton,polynomially ambiguous automaton,efficient algorithm
Conference
abs/0802.3254
ISSN
Citations 
PageRank 
0302-9743
8
0.74
References 
Authors
12
3
Name
Order
Citations
PageRank
Cyril Allauzen169047.64
Mehryar Mohri24502448.21
Ashish Rastogi316110.55