Paper Info
Title
General Algorithms For Testing The Ambiguity Of Finite Automata And The Double-Tape Ambiguity Of Finite-State Transducers
Abstract
We present efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with epsilon-transitions. We give an algorithm for testing the exponential ambiguity of an ant OM at on A in time O(vertical bar A vertical bar(2)(E)), and finite or polynomial ambiguity in time O(vertical bar A vertical bar(3)(E)), where vertical bar A vertical bar(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. Additionally, we give an algorithm to determine in time O(vertical bar A vertical bar(3)(E)) the degree of polynomial ambiguity of a polynomially ambiguous automaton A and present an application of our algorithms to an approximate computation of the entropy of a probabilistic automaton.We also study the double-tape ambiguity of ifinite-stal,e transdui ers. We show that the general problem is undecidable and that it is NP-hard for acyclic transducers, We present a specific analysis of the double-tape ambiguity of transducers with bounded delay. In particular, we give a characterization of double-tape ambiguity for synchronized transducers with zero delay that can be tested in quadratic time and give an algorithm for testing the double-tape ambiguity of transducers with bounded delay.
Year
DOI
Venue
2011
10.1142/S0129054111008477
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE
Field
DocType
Volume
Discrete mathematics,Combinatorics,Polynomial,Automaton,Degree of a polynomial,Algorithm,Finite-state machine,Time complexity,Ambiguity,Probabilistic automaton,Mathematics,Undecidable problem
Journal
22
Issue
ISSN
Citations 
4
0129-0541
5
PageRank 
References 
Authors
0.51
12
3
Name
Order
Citations
PageRank
Cyril Allauzen169047.64
Mehryar Mohri24502448.21
Ashish Rastogi316110.55