One the representation of finite deterministic 2-tape automata

Maryse Pelletier & Jacques Sakarovitc

IBP-Litp 1996/38: Rapport de Recherche Litp / Litp research reports
81 pages - Décembre/December 1996 - Document en anglais.

PostScript : Ko /Kb

Titre / Title: One the representation of finite deterministic 2-tape automata

Résumé : Les automates déterministes à deux bandes sont ceux qui admettent une représentation matricielle préfixe. La construction de Schützenberger sur les représentations, celle qui donne les représentations semi-monomiales pour les fonctions rationnelles, est alors appliquée à cette représentation préfixe afin d'obtenir une nouvelle preuve du fait que la sélection lexicographique d'une relation rationnelle déterministe 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 construct 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 selection of a deterministic rational relation on words is a rational function.

Publications internes Litp 1996 / Litp research reports 1996