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 A in time \(O(|A|_E^2)\), and finite or polynomial ambiguity in time \(O(|A|_E^3)\), 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. 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.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allauzen, C., Mohri, M.: Efficient Algorithms for Testing the Twins Property. Journal of Automata, Languages and Combinatorics 8(2), 117–144 (2003)
Allauzen, C., Mohri, M.: 3-way composition of weighted finite-state transducers. In: CIAA 2008. LNCS, vol. 5148, pp. 262–273. Springer, Heidelberg (2008)
Chan, T., Ibarra, O.H.: On the finite-valuedness problem for sequential machines. Theoretical Computer Science 23, 95–101 (1983)
Cortes, C., Mohri, M., Rastogi, A., Riley, M.: Efficient computation of the relative entropy of probabilistic automata. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 323–336. Springer, Heidelberg (2006)
Cover, T.M., Thomas, J.A.: Elements of Information Theory. John Wiley & Sons, Inc., New York (1991)
Ibarra, O.H., Ravikumar, B.: On sparseness, ambiguity and other decision problems for acceptors and transducers. In: Monien, B., Vidal-Naquet, G. (eds.) STACS 1986. LNCS, vol. 210, pp. 171–179. Springer, Heidelberg (1985)
Jacob, G.: Un algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices. Theoretical Computer Science 5(2), 183–202 (1977)
Kuich, W.: Finite automata and ambiguity. Technical Report 253, Institute für Informationsverarbeitung - Technische Universität Graz und ÖCG (1988)
Mandel, A., Simon, I.: On finite semigroups of matrices. Theoretical Computer Science 5(2), 101–111 (1977)
Mohri, M., Pereira, F.C.N., Riley, M.: Weighted Automata in Text and Speech Processing. In: Proceedings of ECAI 1996, Workshop on Extended finite state models of language, Budapest, Hungary. John Wiley and Sons, Chichester (1996)
Pereira, F., Riley, M.: Speech Recognition by Composition of Weighted Finite Automata. In: Finite State Language Processing. MIT Press, Cambridge (1997)
Ravikumar, B., Ibarra, O.H.: Relating the type of ambiguity of finite automata to the succintness of their representation. SIAM Journal on Computing 18(6), 1263–1282 (1989)
Reutenauer, C.: Propriétés arithmétiques et topologiques des séries rationnelles en variable non commutative. Thèse de troisième cycle, Université Paris VI (1977)
Weber, A.: Über die Mehrdeutigkeit und Wertigkeit von endlichen, Automaten und Transducern. Dissertation, Goethe-Universität Frankfurt am Main (1987)
Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol. 233, pp. 620–629. Springer, Heidelberg (1986)
Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theoretical Computer Science 88(2), 325–349 (1991)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Allauzen, C., Mohri, M., Rastogi, A. (2008). General Algorithms for Testing the Ambiguity of Finite Automata. In: Ito, M., Toyama, M. (eds) Developments in Language Theory. DLT 2008. Lecture Notes in Computer Science, vol 5257. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85780-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-540-85780-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85779-2
Online ISBN: 978-3-540-85780-8
eBook Packages: Computer ScienceComputer Science (R0)