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.
Keywords: 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},
year = {2008},
publisher = {EDP Sciences},
volume = {42},
number = {3},
doi = {10.1051/ita:2008017},
mrnumber = {2434035},
zbl = {1155.68042},
language = {en},
url = {https://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 SP - 553 EP - 581 VL - 42 IS - 3 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ita:2008017/ DO - 10.1051/ita:2008017 LA - en ID - ITA_2008__42_3_553_0 ER -
%0 Journal Article %A Kirsten, Daniel %T A burnside approach to the termination of Mohri's algorithm for polynomially ambiguous Min-Plus-automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2008 %P 553-581 %V 42 %N 3 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ita:2008017/ %R 10.1051/ita:2008017 %G en %F 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) no. 3, pp. 553-581. doi: 10.1051/ita:2008017
[1] and , Efficient algorithms for testing the twins property. Journal of Automata, Languages and Combinatorics 8 (2003) 117-144. | Zbl | MR
[2] and , Rational Series and Their Languages, volume 12 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag, Berlin Heidelberg New York (1984). | Zbl | MR
[3] , and , On the determinization of weighted finite automata. SIAM Journal of Computing (2000) 1502-1531. | Zbl | MR
[4] and , A note on factorization forests of finite height. Theoretical Computer Science 310 (2004) 489-499. | Zbl | MR
[5] , Une caracterisation des fonctions sequentielles et des fonctions sous-sequentielles en tant que relations rationnelles. Theoretical Computer Science 5 (1977) 325-337. | Zbl | MR
[6] and , Image compression using weighted finite automata. Computer and Graphics 17 (1993) 305-313. | MR
[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. | Zbl | MR
[10] , Improved limitedness theorems on finite automata with distance functions. Theoretical Computer Science 72 (1990) 27-38. | Zbl | MR
[11] , New upper bounds to the limitedness of distance automata. Theoretical Computer Science 233 (2000) 19-32. | Zbl | MR
[12] , and , Decidability of the equivalence problem for finitely ambiguous finance automata. International Journal of Algebra and Computation 12 (2002) 445-461. | Zbl | MR
[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). | Zbl | MR
[14] , , , and , Communication complexity method for measuring nondeterminism in finite automata. Information and Computation 172 (2002) 202-217. | Zbl | MR
[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). | Zbl | MR
[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). | Zbl | MR
[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. | Zbl | MR | Numdam
[19] and , On the determinization of weighted automata. Journal of Automata, Languages and Combinatorics 10 (2005) 287-312. | MR
[20] , , and , Deciding unambiguity and sequentiality from a finitely ambiguous max-plus automaton. Theoretical Computer Science 327 (2004) 349-373. | Zbl | MR
[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. | Zbl | MR
[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
[23] and , editors. Semirings, Automata, Languages, volume 5 of Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin (1986). | Zbl | MR
[24] , Limitedness theorem on finite automata with distance functions: An algebraic proof. Theoretical Computer Science 81 (1991) 137-145. | Zbl | MR
[25] , Separating exponentially ambiguous finite automata from polynomially ambiguous finite automata. SIAM Journal of Computing 27 (1998) 1073-1082. | Zbl | MR
[26] , The topological approach to the limitedness problem on distance automata. In J. Gunawardena, editor, Idempotency, pages 88-111. Cambridge University Press (1998). | Zbl | MR
[27] and , The limitedness problem on distance automata: Hashiguchi's method revisited. Theoretical Computer Science 310 (2004) 147-158. | Zbl | MR
[28] and , New results on the star problem in trace monoids. Information and Computation 119 (1995) 240-251. | Zbl | MR
[29] , Finite-state transducers in language and speech processing. Computational Linguistics 23 (1997) 269-311. | MR
[30] and , Automata-Theoretic Aspects of Formal Power Series. Texts and Monographs on Computer Science. Springer-Verlag, Berlin Heidelberg New York (1978). | Zbl | MR
[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). | Zbl | MR
[32] , Factorization forests of finite height. Theoretical Computer Science 72 (1990) 65-94. | Zbl | MR
[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). | Zbl | MR
[34] , On semigroups of matrices over the tropical semiring. RAIRO-Theor. Inf. Appl. 28 (1994) 277-294. | Zbl | MR | Numdam
[35] , Distance automata having large finite distance or finite ambiguity. Mathematical Systems Theory 26 (1993) 169-185. | Zbl | MR
[36] , Finite valued distance automata. Theoretical Computer Science 134 (1994) 225-251. | Zbl | MR
Cité par Sources :
