R. A. Wagner and M. J. Fischer, The string-to-string correction problem, Journal of the ACM (JACM), vol.21, issue.1, pp.168-173, 1974.

S. Henikoff and J. Henikoff, Amino acid substitution matrices from protein blocks, PNAS, vol.89, pp.10915-10919, 1992.

M. Mongeau and D. Sankoff, Comparison of musical sequences, Computers and the Humanities, vol.24, issue.3, pp.161-175, 1990.
URL : https://hal.archives-ouvertes.fr/hal-01098807

J. B. Kruskal and M. Liberman, The symmetric time-warping problem: from continuous to discrete, Time Warps, String Edits, and Macromolecules -The Theory and Practice of Sequence Comparison, 1999.

M. Mohri, Edit-distance of weighted automata: General definitions and algorithms, Int. Journal of Foundations of Computer Science, vol.14, issue.06, pp.957-982, 2003.

D. Hofbauer and J. Waldmann, Deleting string rewriting systems preserve regularity, Theoretical Computer Science, vol.327, issue.3, pp.301-317, 2004.

R. V. Book and F. Otto, String-rewriting systems, String-Rewriting Systems, pp.35-64, 1993.

M. Mohri, Semiring frameworks and algorithms for shortest-distance problems, Journal of Automata, Languages and Combinatorics, vol.7, issue.3, pp.321-350, 2002.

M. Droste and W. Kuich-;-droste, Semirings and formal power series, pp.3-28

, Handbook of Weighted Automata, 2009.

R. C. Backhouse and B. A. Carré, Regular algebra applied to path-finding problems, IMA Journal of Applied Mathematics, vol.15, issue.2, pp.161-186, 1975.

S. Needleman and C. Wunsch, A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology, vol.48, issue.3, pp.443-453, 1970.

E. Ukkonen, Algorithms for approximate string matching, Information and Control, vol.64, pp.100-118, 1985.

M. Mohri, Generic ?-removal algorithm for weighted automata, Int. Conference on Implementation and Application of Automata (CIAA), pp.230-242, 2001.

S. Lombardy and J. Sakarovitch, The removal of weighted ?-transitions, Int. Conference on Implementation and Application of Automata (CIAA), pp.345-352, 2012.
URL : https://hal.archives-ouvertes.fr/hal-00737679

L. Huang, Advanced dynamic programming in semiring and hypergraph frameworks, Int. Committee on Computational Linguistics Conference (COLING), 2008.

S. Dolan, Fun with semirings: A functional pearl on the abuse of linear algebra, Int. Conference on Functional Programming (ICFP), 2013.