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 ,
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 ,
Latteux : A new proof of two theorems about rational transductions, Theoretical Computer Science, vol.8, issue.1, pp.261-263, 1979. ,
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
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
Transductions and Context-Free Languages ,
DOI : 10.1007/978-3-663-09367-1
URL : https://hal.archives-ouvertes.fr/hal-00619779
Quatre premiers chapitres disponibles sur http, p.143, 1979. ,
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
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
ContributionàContribution`Contributionà l'´ etude de Quelques Familles Remarquables de Fonctions Rationelles, Thèse d'´ etat, p.115, 1978. ,
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
Stein : Introduction to Algorithms, p.29, 2001. ,
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
On the Decidability of the Equivalence for k-Valued Transducers, 2008. ,
DOI : 10.1007/978-3-540-85780-8_20
Algèbre catégorique et théorie des automates, p.27, 1967. ,
Automata, Languages, and Machines, volume A, pp.30-41, 1974. ,
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
Decidability results concerning tree transducers, Acta Cybernetica, vol.5, pp.303-314, 1983. ,
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
Synchronized rational relations of finite and infinite words, Theoretical Computer Science, vol.108, issue.1, pp.45-82, 1993. ,
Synchronisation déterministe des automatesàtomatesà délai borné, Theoretical Computer Science, vol.191, issue.13, pp.61-77, 1998. ,
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
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
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
A note on finite-valued and finitely ambiguous transducers, Mathematical Systems Theory, vol.4, issue.1, pp.61-66, 1983. ,
DOI : 10.1007/BF01744569
Ullman : Introduction to Automata Theory, Languages and Computation, p.144, 2001. ,
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
Do rational equivalence relations have regular cross-sections?, Proc. ICALP'85, pp.300-309, 1985. ,
DOI : 10.1007/BFb0015755
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
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
Approche structurelle de quelquesprobì emes de la théorie des automates, Thèse de doctorat, p.12, 2001. ,
On finite semigroups of matrices, Theoretical Computer Science, vol.5, issue.2, pp.101-111, 1977. ,
DOI : 10.1016/0304-3975(77)90001-9
The Burnside problem for semigroups, Journal of Algebra, vol.34, issue.2, pp.292-299, 1975. ,
DOI : 10.1016/0021-8693(75)90184-2
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
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
Schabes : Finite-State Language Processing, p.115, 1997. ,
The Mathematical Theory of L-Systems, p.145, 1980. ,
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
Translation anglaise : Elements of Automata Theory, pp.41-42, 2003. ,
The rational skimming theorem, The Mathematical Foundation of Informatics, pp.157-172, 1999. ,
DOI : 10.1142/9789812703118_0015
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
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
Sur les relations rationnelles, Automata Theory and Formal Languages, 2nd GI Conference, pp.209-213, 1975. ,
DOI : 10.1007/3-540-07407-4_22
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
Equivalence of finite-valued tree transducers is decidable, Mathematical Systems Theory, vol.4, issue.4, pp.285-346, 1994. ,
DOI : 10.1007/BF01192143
Topology of finite graphs, Inventiones Mathematicae, vol.4, issue.3, pp.551-565, 1983. ,
DOI : 10.1007/BF02095993
On the valuedness of finite transducers, Acta Informatica, vol.27, issue.8, pp.749-780, 1989. ,
DOI : 10.1007/BF00264285
On the lengths of values in a finite transducer, Acta Informatica, vol.297, issue.6, pp.663-687, 1992. ,
Decomposing Finite-Valued Transducers and Deciding Their Equivalence, SIAM Journal on Computing, vol.22, issue.1, pp.175-202, 1993. ,
DOI : 10.1137/0222014
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
Economy of description for single-valued transducers, Information and Computation, vol.119, issue.16, pp.327-340, 1995. ,
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