A CONSTRUCTION ON FINITE AUTOMATA THAT HAS REMAINED HIDDEN

We show how a construction on matrix representations of two tape autom ata proposed by Schutzenberger to prove that rational functions are un ambiguous can be given a central role in the theory of relations and f unctions realized by finite automata, in such a way that the other bas ic 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 conse quences of it. (C) 1998 Published by Elsevier Science B.V. All rights reserved.