R. Est-inclus-dans-celui-de-t-?-si, et seulement, pour pour toutétattoutétat final et accessible q de R×W, il existe au moins une différence partielle ? dans m(q) o` u tous les coefficients définis de la forme ? 1

. Ainsi, inclusion de R sur T ? , il suffit de construire la valuation de R × W × G k+1 avec l'algorithme présentéè a la section 4.2, et tester si lesétatslesétats finaux de R×W satisfont la conditionénoncéeconditionénoncée dans la propriété 4.4.3. La complexité de cette construction est bornée par un polynôme sur la

]. A. Bibliographie and . Arnold, Latteux : A new proof of two theorems about rational transductions, Theoretical Computer Science, vol.8, issue.1, pp.261-263, 1979.

M. Béal, Determinization of transducers over finite and infinite words, Theoretical Computer Science, vol.289, issue.1, pp.225-251, 2002.
DOI : 10.1016/S0304-3975(01)00271-7

M. Béal, O. Carton, C. Prieur, and J. Sakarovitch, Squaring transducers: an efficient procedure for deciding functionality and sequentiality, Theoretical Computer Science, vol.292, issue.1, pp.45-63, 2003.
DOI : 10.1016/S0304-3975(01)00214-6

J. Berstel, Transductions and Context-Free Languages
DOI : 10.1007/978-3-663-09367-1
URL : https://hal.archives-ouvertes.fr/hal-00619779

G. Teubner, Quatre premiers chapitres disponibles sur http, p.143, 1979.

M. Blattner and T. Head, Single-valued a-transducers, Journal of Computer and System Sciences, vol.15, issue.3, pp.310-327, 1977.
DOI : 10.1016/S0022-0000(77)80033-0

C. Choffrut, Une caracterisation des fonctions sequentielles et des fonctions sous-sequentielles en tant que relations rationnelles, Theoretical Computer Science, vol.5, issue.3, pp.325-338, 1977.
DOI : 10.1016/0304-3975(77)90049-4
URL : http://doi.org/10.1016/0304-3975(77)90049-4

C. Choffrut, ContributionàContribution`Contributionà l'´ etude de Quelques Familles Remarquables de Fonctions Rationelles, Thèse d'´ etat, p.115, 1978.

C. Choffrut, A generalization of Ginsburg and Rose's characterization of G-S-M mappings, ICALP'79, pp.88-103, 1979.
DOI : 10.1007/3-540-09510-1_8

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. , Stein : Introduction to Algorithms, p.29, 2001.

K. Culik and J. Karhumäki, The equivalence of finite valued transducers (on HDT0L languages) is decidable, Theoretical Computer Science, vol.47, issue.17, pp.71-84, 1986.
DOI : 10.1016/0304-3975(86)90134-9

R. Souza, On the Decidability of the Equivalence for k-Valued Transducers, 2008.
DOI : 10.1007/978-3-540-85780-8_20

S. Eilenberg, Algèbre catégorique et théorie des automates, p.27, 1967.

S. Eilenberg, Automata, Languages, and Machines, volume A, pp.30-41, 1974.

C. C. Elgot and J. E. Mezei, On Relations Defined by Generalized Finite Automata, IBM Journal of Research and Development, vol.9, issue.1, pp.47-68, 1965.
DOI : 10.1147/rd.91.0047

Z. Esik, Decidability results concerning tree transducers, Acta Cybernetica, vol.5, pp.303-314, 1983.

P. C. Fischer and A. L. Rosenberg, Multitape one-way nonwriting automata, Journal of Computer and System Sciences, vol.2, issue.1, pp.88-101, 1968.
DOI : 10.1016/S0022-0000(68)80006-6
URL : http://doi.org/10.1016/s0022-0000(68)80006-6

. Ch, J. Frougny, and . Sakarovitch, Synchronized rational relations of finite and infinite words, Theoretical Computer Science, vol.108, issue.1, pp.45-82, 1993.

. Ch, J. Frougny, and . Sakarovitch, Synchronisation déterministe des automatesàtomatesà délai borné, Theoretical Computer Science, vol.191, issue.13, pp.61-77, 1998.

S. Ginsburg and G. F. Rose, A characterization of machine mappings, Journal canadien de math??matiques, vol.18, issue.0, pp.381-388, 1966.
DOI : 10.4153/CJM-1966-040-3

F. Gire, Two decidability problems for infinite words, Information Processing Letters, vol.22, issue.3, pp.135-140, 1986.
DOI : 10.1016/0020-0190(86)90058-X

E. Gurari and O. Ibarra, The complexity of decision problems for finite-turn multicounter machines, Journal of Computer and System Sciences, vol.22, issue.2, pp.220-229, 1981.
DOI : 10.1016/0022-0000(81)90028-3

E. Gurari and O. Ibarra, A note on finite-valued and finitely ambiguous transducers, Mathematical Systems Theory, vol.4, issue.1, pp.61-66, 1983.
DOI : 10.1007/BF01744569

J. E. Hopcroft, R. Motwani, and J. D. , Ullman : Introduction to Automata Theory, Languages and Computation, p.144, 2001.

G. Jacob, UN algorithme calculant le cardinal, fini ou infini, des demi-groupes de matrices, Theoretical Computer Science, vol.5, issue.2, pp.183-204, 1977.
DOI : 10.1016/0304-3975(77)90006-8
URL : http://doi.org/10.1016/0304-3975(77)90006-8

J. H. Johnson, Do rational equivalence relations have regular cross-sections?, Proc. ICALP'85, pp.300-309, 1985.
DOI : 10.1007/BFb0015755

J. H. Johnson, Rational equivalence relations, Theoretical Computer Science, vol.47, issue.3, pp.39-60, 1986.
DOI : 10.1016/0304-3975(86)90132-5
URL : http://dx.doi.org/10.1016/0304-3975(86)90132-5

K. Kobayashi, Classification of formal languages by functional binary transductions, Information and Control, vol.15, issue.1, pp.95-109, 1969.
DOI : 10.1016/S0019-9958(69)90651-2

S. Lombardy, Approche structurelle de quelquesprobì emes de la théorie des automates, Thèse de doctorat, p.12, 2001.

A. Mandel and I. Simon, On finite semigroups of matrices, Theoretical Computer Science, vol.5, issue.2, pp.101-111, 1977.
DOI : 10.1016/0304-3975(77)90001-9

R. Mcnaughton and Y. Zalcstein, The Burnside problem for semigroups, Journal of Algebra, vol.34, issue.2, pp.292-299, 1975.
DOI : 10.1016/0021-8693(75)90184-2

M. Mohri, On some applications of finite-state automata theory to natural language processing, Natural Language Engineering, vol.2, issue.1, pp.1-20, 1995.
DOI : 10.1017/S135132499600126X

M. Pelletier and J. Sakarovitch, On the representation of finite deterministic 2-tape automata, Theoretical Computer Science, vol.225, issue.1-2, pp.1-63, 1999.
DOI : 10.1016/S0304-3975(98)00179-0

E. Roche and Y. , Schabes : Finite-State Language Processing, p.115, 1997.

G. Rozenberg and A. Salomaa, The Mathematical Theory of L-Systems, p.145, 1980.

J. Sakarovitch, A construction on finite automata that has remained hidden, Theoretical Computer Science, vol.204, issue.1-2, pp.205-231, 1998.
DOI : 10.1016/S0304-3975(98)00040-1

J. Sakarovitch, Translation anglaise : Elements of Automata Theory, pp.41-42, 2003.

J. Sakarovitch, The rational skimming theorem, The Mathematical Foundation of Informatics, pp.157-172, 1999.
DOI : 10.1142/9789812703118_0015

J. Sakarovitch, R. De-souza, E. Ochma´nskiochma´nski, and J. Tyszkiewicz, On the Decidability of Bounded Valuedness for Transducers, Lecture Notes in Computer Science, vol.5162, pp.588-600, 2008.
DOI : 10.1007/978-3-540-85238-4_48

J. Sakarovitch and R. De-souza, On the decomposition of k-valued rational relations, Proceedings of 192 BIBLIOGRAPHIE STACS 2008. disponible sur http://stacs-conf.org (` a para??trepara??tre dans Theory of Computing Systems, pp.621-632, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00256231

M. P. Schützenberger, Sur les relations rationnelles, Automata Theory and Formal Languages, 2nd GI Conference, pp.209-213, 1975.
DOI : 10.1007/3-540-07407-4_22

M. P. Schützenberger, Sur les relations rationnelles entre monoides libres, Theoretical Computer Science, vol.3, issue.2, pp.243-259, 1976.
DOI : 10.1016/0304-3975(76)90026-8

H. Seidl, Equivalence of finite-valued tree transducers is decidable, Mathematical Systems Theory, vol.4, issue.4, pp.285-346, 1994.
DOI : 10.1007/BF01192143

J. R. Stallings, Topology of finite graphs, Inventiones Mathematicae, vol.4, issue.3, pp.551-565, 1983.
DOI : 10.1007/BF02095993

A. Weber, On the valuedness of finite transducers, Acta Informatica, vol.27, issue.8, pp.749-780, 1989.
DOI : 10.1007/BF00264285

A. Weber, On the lengths of values in a finite transducer, Acta Informatica, vol.297, issue.6, pp.663-687, 1992.

A. Weber, Decomposing Finite-Valued Transducers and Deciding Their Equivalence, SIAM Journal on Computing, vol.22, issue.1, pp.175-202, 1993.
DOI : 10.1137/0222014

A. Weber, Decomposing a $k$-valued transducer into $k$ unambiguous ones, RAIRO - Theoretical Informatics and Applications, vol.30, issue.5, pp.379-413, 1996.
DOI : 10.1051/ita/1996300503791

A. Weber and R. Klemm, Economy of description for single-valued transducers, Information and Computation, vol.119, issue.16, pp.327-340, 1995.

A. Weber and H. Seidl, On the degree of ambiguity of finite automata, Theoretical Computer Science, vol.88, issue.2, pp.325-349, 1991.
DOI : 10.1016/0304-3975(91)90381-B