GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS
Authors:
- 1 June 2011
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- Vol. 22 (04) , 883-904
Abstract
We present efficient algorithms for testing the finite, polynomial, and exponential ambiguity of finite automata with ε-transitions. We give an algorithm for testing the exponential ambiguity of an automaton A in time [Formula: see text], and finite or polynomial ambiguity in time [Formula: see text], 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. Additionally, we give an algorithm to determine in time [Formula: see text] 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 finite-state transducers. 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.Keywords
This publication has 9 references indexed in Scilit:
- ON THE COMPUTATION OF THE RELATIVE ENTROPY OF PROBABILISTIC AUTOMATAInternational Journal of Foundations of Computer Science, 2008
- EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMSInternational Journal of Foundations of Computer Science, 2003
- Elements of Information Theory2001
- On the degree of ambiguity of finite automataTheoretical Computer Science, 1991
- Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their RepresentationSIAM Journal on Computing, 1989
- On the finite-valuedness problem for sequential machinesTheoretical Computer Science, 1988
- UN algorithme calculant le cardinal, fini ou infini, des demi-groupes de matricesTheoretical Computer Science, 1977
- On finite semigroups of matricesTheoretical Computer Science, 1977
- A variant of a recursively unsolvable problemBulletin of the American Mathematical Society, 1946