The Schützenberger construct and two applications

J. sakarovitch

IBP-Litp 1996/30: Rapport de Recherche Litp / Litp research reports
26 pages - Octobre/October 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: The Schützenberger construct and two applications

Résumé : Nous montrons comment une construction sur la représentation matricielle des automates à deux bandes proposée par Schützenberger pour prouver que toute fonction rationnelle est non ambiguë est en fait au coeur de la théorie des relations et fonctions réalisées par automates finis et permet d'établir naturellement les autres résultats fondamentaux de la théorie comme le «Cross-Section Theorem», son dual, le théorème d'uniformisation rationnelle ou le théorème de décomposition des fonctions rationnelles en fonctions séquentielles.

Abstract : We show how a construction on matrix representations of two tape automata proposed by Schützenberger to prove that rational function are unambiguous can be given a central rôle in the theory of relations and functions realized by finite automata, in such a way that the other basic results such as the "Cross-Section Theorem", its dual the theorem of rational uniformisation, or the decomposition theorem of rational functions into sequential functions, appear as direct and formal consequences of it.

Publications internes Litp 1996 / Litp research reports 1996