Voir la notice de l'article provenant de la source Numdam
Consider partial maps with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one that recognize the same series.
@article{ITA_2006__40_1_1_0,
author = {Lombardy, Sylvain and Mairesse, Jean},
title = {Series which are both max-plus and min-plus rational are unambiguous},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {1--14},
publisher = {EDP-Sciences},
volume = {40},
number = {1},
year = {2006},
doi = {10.1051/ita:2005042},
mrnumber = {2197280},
zbl = {1085.68081},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005042/}
}
TY - JOUR AU - Lombardy, Sylvain AU - Mairesse, Jean TI - Series which are both max-plus and min-plus rational are unambiguous JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 1 EP - 14 VL - 40 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005042/ DO - 10.1051/ita:2005042 LA - en ID - ITA_2006__40_1_1_0 ER -
%0 Journal Article %A Lombardy, Sylvain %A Mairesse, Jean %T Series which are both max-plus and min-plus rational are unambiguous %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 1-14 %V 40 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005042/ %R 10.1051/ita:2005042 %G en %F ITA_2006__40_1_1_0
Lombardy, Sylvain; Mairesse, Jean. Series which are both max-plus and min-plus rational are unambiguous. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 1, pp. 1-14. doi: 10.1051/ita:2005042
Cité par Sources :