Affordable Access

On decision problems on word transducers with origin semantics

  • Bose, Sougata
Publication Date
Mar 12, 2021
External links


The origin semantics for word transducers was introduced by Bojańczyk in 2014 in order to obtain a machine-independent characterization for word-to-word functions defined by transducers. Our primary goal was to study some classical decision problems for transducers in the origin semantics, such as the containment and the equivalence problem. We showed that these problems become decidable in the origin semantics, even though the classical version is undecidable.Motivated by the observation that the origin semantics is more fine-grained than classical semantics, we defined resynchronizers as a way to describe distortions of origins, and to study the above problems in a more relaxed way. We extended the model of rational resynchronizers, introduced by Filiot et al. for one-way transducers, to regular resynchronizers, which work for larger classes of transducers.We studied the two variants of the containment up to resynchronizer problem, which asks if a transducer is contained in another up to a distortion specified by a resynchronizer. We showed that the problem is decidable when the resynchronizer is given as part of the input. When the resynchronizer is not specified in the input, we aimed to synthesize such a resynchronizer, whenever possible. We call this the synthesis problem for resynchronizers and show that it is undecidable in general. We identified some restricted cases when the problem becomes decidable. We also studied the one-way resynchronizability problem, which asks whether a given two-way transducer is resynchronizable in a one-way transducer, and showed that this problem is decidable as well.

Report this publication


Seen <100 times