Jan Martens: Resynchronizability of origin transducers

Event Details

Origin semantics introduced by Bojańczyk is a fine grained semantics for transducers, that not only expresses the relation between input and output words, but also includes a function that given an output position returns the input position where it was produced: the origin. In this talk we’ll discuss resynchronizations, a tool to relax the notion of origin while maintaining decidable properties. The talk specifically focusses on the notion of containment up-to some unknown resynchronization. This relation forms a pre-order strictly in between classical and origin containment. We show this containment is undecidable, which was a recent open problem. This is done using a notion of limited traversal which syntactically classifies the non-existence of a resynchronization.