[comp.theory] finite input-output automata

benachi@loria.crin.fr (Benachi Saad) (03/19/91)

I would appreciate any comments thoughts, references to works related to the
following subject :

Suppose we have a finite input-output automaton M = (Q, A, d, s, q0, F)
where M' = (Q, A, d, q0, F) is a classical finite automaton and s is an output
function.
The behaviour of M for an input word u is defined by the following algorithm :
  Let p be the current state and a the current letter ;
 (1) If there is a state r such that d(p, a) = r Then
        go to the state r;
     Else /* there is no transition from p labelled with a */
        write a on the output tape
     Fi
  read the next letter ;
  repeat (1) until the read-head reaches the right end of the input word u ;
We have as a result a state q and an output word v.
We call such a process a pass of M on u starting in state p and write :
g(p, u) = (q, v).

We say that M goes in an new pass if M starts with as current state q and input
word v and write g^2(p, u) = g(g(q, v)).
It is easy to see that after a number n of passes we have :
 g^n(p, u) = (q, empty_word) or 
 g^n(p, u) = (q, v) and g(q, v) = (q, v)
Define the language L(M, n) accepted by M in a finite number n of passes to be the
set of words :
{ u such that there exist an integer l <= n ; g^l(q0, u) = (qf, empty word)
  and qf is in F }

Conjecture : L(M, n) is recognizable ????

Thanks in advance.