Transducers With Origin Information

Mikołaj Bojańczyk
Warsaw University
Friday, 27 February, 2015 - 14:00
NO Solvay (5th floor)

A transducer with origin information inputs a word, and produces not just an output word, but also a mapping from positions of the output word to positions of the input word. This mapping is called the origin information. For instance, over a one letter input alphabet, the identity function and the reverse function are the same functions without origin information, but are different functions with origin information. I will argue that having origin information in the semantics makes the theory of transducers easier and perhaps better behaved.