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 :
[img]
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://www.archipel.uqam.ca/id/eprint/8195

Statistiques

Voir les statistiques sur cinq ans...