Restarting Transducers, Regular Languages, and Rational Relations

Research paper by Norbert Hundeshagen, Friedrich Otto

Indexed on: 14 Oct '14Published on: 14 Oct '14Published in: Theory of Computing Systems


A (nonforgetting) restarting transducer is a (nonforgetting) restarting automaton that is equipped with an output function. Accordingly, restarting transducers compute binary relations, and deterministic restarting transducers compute functions. Here we characterize the rational functions and some of their proper subclasses by certain types of deterministic restarting transducers with window size one. As a preliminary step we prove that the monotone variants of the nonforgetting R- and the nonforgetting deterministic RR-automata with window size one only accept regular languages.