Minimization of Rational Word Functions

Reutenauer, Christophe et Schutzenberger, Marcel-Paul (1991). « Minimization of Rational Word Functions ». SIAM Journal on Computing, 20(4), pp. 669-685.

Fichier(s) associé(s) à ce document :

Prévisualisation	PDF Télécharger (3MB)

Résumé

Rational functions from a free monoid into another are characterized by the finiteness of the index of some congruence naturally associated with the function. A sequential bimachine is constructed computing the function, which is completely canonical, and in some sense minimal. This generalizes the Nerode criterion and the minimal automaton of a rational language, and similar results for sequential functions.

Type:	Article de revue scientifique
Mots-clés ou Sujets:	rational function, sequential bimachine
Unité d'appartenance:	Faculté des sciences > Département de mathématiques
Déposé par:	Christophe Reutenauer
Date de dépôt:	19 avr. 2016 19:09
Dernière modification:	27 avr. 2016 18:32
Adresse URL :	http://archipel.uqam.ca/id/eprint/8195

Modifier les métadonnées (propriétaire du document)

Statistiques