Mikołaj Bojańczyk

Transducers with origin information


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

This paper is about transducers. The idea 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.

 

Leave a Reply

Your email address will not be published.