General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers

Cyril Allauzen, Mehryar Mohri, Ashish Rastogi

Research output: Contribution to journalArticlepeer-review

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 O(|A|E2), and finite or polynomial ambiguity in time O(|A|E3), 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 O(|A|E3) 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.

Original languageEnglish (US)
Pages (from-to)883-904
Number of pages22
JournalInternational Journal of Foundations of Computer Science
Volume22
Issue number4
DOIs
StatePublished - Jun 2011

ASJC Scopus subject areas

  • Computer Science (miscellaneous)

Fingerprint Dive into the research topics of 'General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers'. Together they form a unique fingerprint.

Cite this