We use cookies on this website. Our privacy policy explains what cookies are and how they are being used here. If you continue to access our website, we'll assume that you consent to receiving cookies from this website.

What do you do if a computational object fails a specification? An obvious approach is to repair this object is such a way that satisfies the new constraints. Before repairing it, one would like to know a priori whether the amount of modifications needed is bounded with respect to my initial specification and, if not, whether the maximum number of modifications per elements is below a fraction.

In this talk, I will present our recent results about repairing words over regular languages. These results are divided into two main problems. The former problem ask whether it is possible to repair each instance of a regular language language into another language with a bounded number of modifications. One of our main contributions is to isolate the complexity of the "bounded repair problem" based on a characterization of the pairs of regular languages that admit such a repair. We also study this problem when the repair strategy is restricted to a streaming access over the instance and we show that there are surprising connections between streaming and non-streaming repair. For the latter problem, we study the maximum number of modifications per character needed in order to repair any string in one regular language into another language. We show that indeed this value is rational and can be effectively computed for any pair of regular languages. The algorithm to be presented is quite non-trivial and uses a local determinization procedure applicable to a subclass of distance automata.