We show that the termination of Mohri's algorithm is decidable for polynomially ambiguous weighted finite automata over the tropical semiring which gives a partial answer to a question by Mohri [29]. The proof relies on an improvement of the notion of the twins property and a Burnside type characterization for the finiteness of the set of states produced by Mohri's algorithm.
@article{ITA_2008__42_3_553_0,
author = {Kirsten, Daniel},
title = {A burnside approach to the termination of Mohri's algorithm for polynomially ambiguous Min-Plus-automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {42},
year = {2008},
pages = {553-581},
doi = {10.1051/ita:2008017},
mrnumber = {2434035},
zbl = {1155.68042},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2008__42_3_553_0}
}
Kirsten, Daniel. A burnside approach to the termination of Mohri's algorithm for polynomially ambiguous Min-Plus-automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 553-581. doi : 10.1051/ita:2008017. http://gdmltest.u-ga.fr/item/ITA_2008__42_3_553_0/
[1] and , Efficient algorithms for testing the twins property. Journal of Automata, Languages and Combinatorics 8 (2003) 117-144. | MR 2000615 | Zbl 1089.68049
[2] and , Rational Series and Their Languages, volume 12 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin Heidelberg New York (1984). | MR 971022 | Zbl 0668.68005
[3] , and , On the determinization of weighted finite automata. SIAM Journal of Computing (2000) 1502-1531. | MR 1813961 | Zbl 0980.68065
[4] and , A note on factorization forests of finite height. Theoretical Computer Science 310 (2004) 489-499. | MR 2020356 | Zbl 1071.68038
[5] , Une caracterisation des fonctions sequentielles et des fonctions sous-sequentielles en tant que relations rationnelles. Theoretical Computer Science 5 (1977) 325-337. | MR 504457 | Zbl 0376.94022
[6] and , Image compression using weighted finite automata. Computer and Graphics 17 (1993) 305-313. | MR 1265078
[7] and , Approximate reasoning in semi-structured databases. In 8th International Workshop on Knowledge Representation meets Databases (KRDB2001), M. Lenzerini et al., Eds. volume 45 of CEUR Workshop Proceedings (2001).
[8] , Low Bit-Rate Image and Video Coding with Weighted Finite Automata. PhD thesis, Universität Würzburg (1999).
[9] , Algorithms for determining relative star height and star height. Information and Computation 78 (1988) 124-169. | MR 955580 | Zbl 0668.68081
[10] , Improved limitedness theorems on finite automata with distance functions. Theoretical Computer Science 72 (1990) 27-38. | MR 1065598 | Zbl 0693.68031
[11] , New upper bounds to the limitedness of distance automata. Theoretical Computer Science 233 (2000) 19-32. | MR 1732175 | Zbl 0952.68082
[12] , and , Decidability of the equivalence problem for finitely ambiguous finance automata. International Journal of Algebra and Computation 12 (2002) 445-461. | MR 1910688 | Zbl 1007.68115
[13] , , , and , Measures of nondeterminism in finite automata. In ICALP'00 Proceedings, volume 1853 of Lecture Notes in Computer Science, U. Montanari et al., Eds. pages 199-210. Springer-Verlag, Berlin (2000). | MR 1795894 | Zbl 0973.68114
[14] , , , and , Communication complexity method for measuring nondeterminism in finite automata. Information and Computation 172 (2002) 202-217. | MR 1881189 | Zbl 1009.68067
[15] and , On sparseness, ambiguity and other decision problems for acceptors and transducers. In STACS'86 Proceedings, volume 210 of Lecture Notes in Computer Science, B. Monien and G. Vidal-Naquet, Eds. pages 171-179. Springer-Verlag, Berlin (1986). | MR 827734 | Zbl 0605.68080
[16] , and , Similarity enrichments in image compression through weighted finite automata. In COCOON'00 Proceedings, volume 1858 of Lecture Notes in Computer Science, pages 447-456. Springer-Verlag, Berlin (2000). | MR 1866152 | Zbl 0988.68639
[17] , Refinements of Data Compression using Weighted Finite Automata. PhD thesis, Universität Siegen (2001).
[18] , Distance desert automata and the star height problem. RAIRO-Theor. Inf. Appl. 39 (2005) 455-509. | Numdam | MR 2157045 | Zbl 1082.20041
[19] and , On the determinization of weighted automata. Journal of Automata, Languages and Combinatorics 10 (2005) 287-312. | MR 2285332 | Zbl pre05141500
[20] , , and , Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science 327 (2004) 349-373. | MR 2098312 | Zbl 1071.68035
[21] , The equality problem for rational series with multiplicities in the tropical semiring is undecidable. International Journal of Algebra and Computation 4 (1994) 405-425. | MR 1297148 | Zbl 0834.68058
[22] , Semirings and formal power series. In G. Rozenberg and A. Salomaa, editors, Handbook of Formal Languages, Vol. 1, Word, Language, Grammar, pages 609-677. Springer-Verlag, Berlin (1997). | MR 1469992
[23] and , editors. Semirings, Automata, Languages, volume 5 of Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin (1986). | MR 817983 | Zbl 0582.68002
[24] , Limitedness theorem on finite automata with distance functions: An algebraic proof. Theoretical Computer Science 81 (1991) 137-145. | MR 1103104 | Zbl 0729.68049
[25] , Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM Journal of Computing 27 (1998) 1073-1082. | MR 1622009 | Zbl 0911.68144
[26] , The topological approach to the limitedness problem on distance automata. In J. Gunawardena, editor, Idempotency, pages 88-111. Cambridge University Press (1998). | MR 1608386 | Zbl 0898.68049
[27] and , The limitedness problem on distance automata: Hashiguchi's method revisited. Theoretical Computer Science 310 (2004) 147-158. | MR 2020340 | Zbl 1071.68045
[28] and , New results on the star problem in trace monoids. Information and Computation 119 (1995) 240-251. | MR 1334466 | Zbl 0832.68074
[29] , Finite-state transducers in language and speech processing. Computational Linguistics 23 (1997) 269-311. | MR 1713412
[30] and , Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs on Computer Science. Springer-Verlag, Berlin Heidelberg New York (1978). | MR 483721 | Zbl 0377.68039
[31] , Recognizable sets with multiplicities in the tropical semiring. In M. P. Chytil et al., editors, MFCS'88 Proceedings, volume 324 of Lecture Notes in Computer Science, pages 107-120. Springer-Verlag, Berlin (1988). | MR 1023416 | Zbl 0656.68086
[32] , Factorization forests of finite height. Theoretical Computer Science 72 (1990) 65-94. | MR 1065601 | Zbl 0693.68044
[33] , A short proof of the factorization forest theorem. In M. Nivat and A. Podelski, Eds. Tree Automata and Languages, pages 433-438. Elsevier Science Publishers B.V. (1992). | MR 1196747 | Zbl 0798.68085
[34] , On semigroups of matrices over the tropical semiring. RAIRO-Theor. Inf. Appl. 28 (1994) 277-294. | Numdam | MR 1282449 | Zbl 0888.68086
[35] , Distance automata having large finite distance or finite ambiguity. Mathematical Systems Theory 26 (1993) 169-185. | MR 1196156 | Zbl 0771.68088
[36] , Finite valued distance automata. Theoretical Computer Science 134 (1994) 225-251. | MR 1299375 | Zbl 0938.68709