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) no. 3, pp. 553-581.

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.

DOI : https://doi.org/10.1051/ita:2008017
Classification : 68Q45,  68Q70,  20M35
Mots clés : weighted automata, tropical semiring, determinization
@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},
pages = {553--581},
publisher = {EDP-Sciences},
volume = {42},
number = {3},
year = {2008},
doi = {10.1051/ita:2008017},
zbl = {1155.68042},
mrnumber = {2434035},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2008017/}
}
TY  - JOUR
AU  - Kirsten, Daniel
TI  - A burnside approach to the termination of Mohri's algorithm for polynomially ambiguous Min-Plus-automata
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
DA  - 2008///
SP  - 553
EP  - 581
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2008017/
UR  - https://zbmath.org/?q=an%3A1155.68042
UR  - https://www.ams.org/mathscinet-getitem?mr=2434035
UR  - https://doi.org/10.1051/ita:2008017
DO  - 10.1051/ita:2008017
LA  - en
ID  - ITA_2008__42_3_553_0
ER  - 
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) no. 3, pp. 553-581. doi : 10.1051/ita:2008017. http://www.numdam.org/articles/10.1051/ita:2008017/

[1] C. Allauzen and M. Mohri, Efficient algorithms for testing the twins property. Journal of Automata, Languages and Combinatorics 8 (2003) 117-144. | MR 2000615 | Zbl 1089.68049

[2] J. Berstel and C. Reutenauer, 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] A.L. Buchsbaum, R. Giancarlo and J.R. Westbrook, On the determinization of weighted finite automata. SIAM Journal of Computing (2000) 1502-1531. | MR 1813961 | Zbl 0980.68065

[4] J. Chalopin and H. Leung, A note on factorization forests of finite height. Theoretical Computer Science 310 (2004) 489-499. | MR 2020356 | Zbl 1071.68038

[5] C. Choffrut, 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] K. Culik Ii and J. Kari, Image compression using weighted finite automata. Computer and Graphics 17 (1993) 305-313. | MR 1265078

[7] G. Grahne and A. Thomo, 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] U. Hafner, Low Bit-Rate Image and Video Coding with Weighted Finite Automata. PhD thesis, Universität Würzburg (1999).

[9] K. Hashiguchi, Algorithms for determining relative star height and star height. Information and Computation 78 (1988) 124-169. | MR 955580 | Zbl 0668.68081

[10] K. Hashiguchi, Improved limitedness theorems on finite automata with distance functions. Theoretical Computer Science 72 (1990) 27-38. | MR 1065598 | Zbl 0693.68031

[11] K. Hashiguchi, New upper bounds to the limitedness of distance automata. Theoretical Computer Science 233 (2000) 19-32. | MR 1732175 | Zbl 0952.68082

[12] K. Hashiguchi, K. Ishiguro and S. Jimbo, 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] J. Hromkovič, J. Karhumäki, H. Klauck, G. Schnitger and S. Seibert, 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] J. Hromkovič, J. Karhumäki, H. Klauck, G. Schnitger and S. Seibert, Communication complexity method for measuring nondeterminism in finite automata. Information and Computation 172 (2002) 202-217. | MR 1881189 | Zbl 1009.68067

[15] O. Ibarra and B. Ravikumar, 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] Z. Jiang, B. Litov and O. De Vel, 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] F. Katritzke, Refinements of Data Compression using Weighted Finite Automata. PhD thesis, Universität Siegen (2001).

[18] D. Kirsten, Distance desert automata and the star height problem. RAIRO-Theor. Inf. Appl. 39 (2005) 455-509. | Numdam | MR 2157045 | Zbl 1082.20041

[19] D. Kirsten and I. Mäurer, On the determinization of weighted automata. Journal of Automata, Languages and Combinatorics 10 (2005) 287-312. | MR 2285332

[20] I. Klimann, S. Lombardy, J. Mairesse and C. Prieur, Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science 327 (2004) 349-373. | MR 2098312 | Zbl 1071.68035

[21] D. Krob, 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] W. Kuich, 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] W. Kuich and A. Salomaa, 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] H. Leung, Limitedness theorem on finite automata with distance functions: An algebraic proof. Theoretical Computer Science 81 (1991) 137-145. | MR 1103104 | Zbl 0729.68049

[25] H. Leung, Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM Journal of Computing 27 (1998) 1073-1082. | MR 1622009 | Zbl 0911.68144

[26] H. Leung, 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] H. Leung and V. Podolskiy, The limitedness problem on distance automata: Hashiguchi's method revisited. Theoretical Computer Science 310 (2004) 147-158. | MR 2020340 | Zbl 1071.68045

[28] Y. Métivier and G. Richomme, New results on the star problem in trace monoids. Information and Computation 119 (1995) 240-251. | MR 1334466 | Zbl 0832.68074

[29] M. Mohri, Finite-state transducers in language and speech processing. Computational Linguistics 23 (1997) 269-311. | MR 1713412

[30] A. Salomaa and M. Soittola, 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] I. Simon, 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] I. Simon, Factorization forests of finite height. Theoretical Computer Science 72 (1990) 65-94. | MR 1065601 | Zbl 0693.68044

[33] I. Simon, 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] I. Simon, On semigroups of matrices over the tropical semiring. RAIRO-Theor. Inf. Appl. 28 (1994) 277-294. | Numdam | MR 1282449 | Zbl 0888.68086

[35] A. Weber, Distance automata having large finite distance or finite ambiguity. Mathematical Systems Theory 26 (1993) 169-185. | MR 1196156 | Zbl 0771.68088

[36] A. Weber, Finite valued distance automata. Theoretical Computer Science 134 (1994) 225-251. | MR 1299375 | Zbl 0938.68709

Cité par Sources :