Restarting transducers, regular languages, and rational relations (Q493655)

The paper deals with variants of finite state automata equipped with the ability to delete a currently scanned letter of the input word and then move its head back to the beginning of the input, without forgetting the current state; they are called non-forgetting restarting automata with read/write window of size one. Additionally, these automata are required to be monotone, in the sense that the distance between erased letters and the end of the word does not increase. First, it is proved that such automata accept only regular languages. Then, transducers with such underlying automata are studied. Certain variants of these transducers are proved to define exactly some basic classes of rational relations; in particular, it is shown that deterministic transducers, which are not required to move the head to the beginning immediately after deleting a letter, define precisely all rational functions.