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

Voir la notice de l'article provenant de la source Numdam

MR Zbl

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 
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
@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

Cité par Sources :