1. Mikołaj Bojańczyk
   Transducers with Origin Information. ICALP (2), 2014   PDF

2. Mikołaj Bojańczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle
   Which Classes of Origin Graphs Are Generated by Transducers. ICALP, 2017   PDF

The idea proposed in [1] is to change the semantics of a transducer, by adding information about which positions in the output originate from which positions in the input. Under such semantics, called origin semantics, fewer transducers are equivalent to each other, e.g. the reverse and identity transformations over a one letter alphabet are not equivalent under origin semantics, but they are equivalent under standard semantics. The paper shows that with origin semantics, many technical and combinatorial problems go away. There is also an implicit and debatable philosophical point, which is that origin semantics better reflects the “true essence” of a transducer, because when thinking of a transducer one also typically has in mind some origin information. Here are some slides.

Paper [2] continues the work on origin semantics. The origin semantics of a transduction can be seen as a set of graphs, which consist of an input string, an output string, and arrows from positions of the output to positions in the input which describe the origin. In [2], we study when a set of such graphs (“origin graphs”) arises from regular transductions. We identify such sets in terms of structural conditions, such as bounded treewidth or bounded outdegree for origins.