On the lexicographic uniformisation of deterministic 2-tape automata

M. Pelletier, J. Sakarovitch

IBP-Litp 1994/37: Rapport de Recherche Litp / Litp research reports
8 pages - Décembre/December 1994 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: On the lexicographic uniformisation of deterministic 2-tape automata

Résumé : Nous montrons tout d'abord que les automates à deux bandes déterministes sont exactement ceux qui ont une représentation matricielle préfixe. Puis nous appliquons à cette représentation préfixe la construction de Schützenberger (celle qui donne des représentations semi-monomiales pour les fonctions rationnelles) afin d'obtenir une nouvelle preuve du fait que la sélection lexicographique des relations déterministes est une fonction rationnelle.

Abstract : It is first shown that deterministic 2-tape automata are characterized as those which can be given a prefix matrix representation. Schützenberger construction on representations, the one that gives semi-monomial representations for rational functions of words, is then applied to this prefix representation in order to obtain a new proof of the fact that the lexicographic uniformisation of deterministic relations on word is a rational function.

Publications internes Litp 1994 / Litp research reports 1994