Measuring the difficulty of a sequence-to-sequence problem using automata theory
Finite-state transducers capture a class of seq2seq problems that correspond to the notion of regular languages, which could be thought of as the &quot;easiest&quot; problems in automata theory.  Your example function $f$ can be implemented by a finite-state transducer.