by Marie-Pierre Béal, Olivier Carton, Christophe Prieur and Jacques Sakarovitch
Ce papier présente une construction sur les transducteurs qui donne une nouvelle preuve conceptuelle pour deux résultats classiques de décidabilité sur les transducteurs : on peut décider si un transducteur fini réalise une relation fonctionnelle et s'il résultats une relation séquentielle. Il en résulte un alforithme polynomial pour les deux procédures de décision.
We described here a construction on transducers that give a new conceptual proof for two classical decidability results on transducers: it is decidable whether a finite transducer realizes a functional relation, and whether a finite transducer realizes a sequential relation. A better complexity follows then for the two decision procedures.
PostScript of short version and long version