Research: Classes of Origin Graphs generated by Transducers

Advisor: Krishna S.

Origin graphs are graphs over pairs of words (input, output), with input edges, output edges andorigin edges - edges mapping each output position to an input position. Transducers naturally recognize sets of origin graphs. We worked on characterizing the sets of origin graphs recognized by a ω-Streaming String Transducer (ω-SST).