General Algorithms for Testing the Ambiguity of Finite Automata

Simple item page
dc.creatorAllauzen, Cyril
dc.creatorMohri, Mehryar
dc.creatorRastogi, Ashish
dc.date2008-02-22
dc.date.accessioned2026-07-07T09:22:44Z
dc.date.available2026-07-07T09:22:44Z
dc.descriptionThis 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 $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.
dc.identifierhttps://arxiv.org/abs/0802.3254
dc.identifierhttp://arxiv.org/abs/0802.3254
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/155480
dc.subjectComputational Complexity
dc.titleGeneral Algorithms for Testing the Ambiguity of Finite Automata
dc.typetext

Files

Collections

arXiv