On the representation of finite deterministic 2-tape automata

AbstractThis paper presents properties of relations between words that are realized by deterministic finite 2-tape automata. It has been made as complete as possible, and is structured by the systematic use of the matrix representation of automata. 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