Geodesic
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 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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 : 10.1051/ita:2008017
Classification : 68Q45, 68Q70, 20M35
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 = {http://geodesic.mathdoc.fr/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  - http://geodesic.mathdoc.fr/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 http://geodesic.mathdoc.fr/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

Cité par Sources :