Bounded Repairability of Word Languages

What do you do if a computational object (e.g. program trace) fails a specifica-tion? An obvious approach is to perform a repair: modify the object minimally to get something that satisfies the constraints. This approach has been in-vestigated in the database community, for integrity constraints, and in the AI community for propositional logics. Here we study how difficult it is to repair a document in the form of a string. Specifically, we consider number of edits that must be applied to an input string in order to satisfy a given target lan-guage. This number may be unbounded; our main contribution is to isolate the complexity of the bounded repair problem based on a characterization of the regular languages that admit bounded repairr. We consider the settings where the repair strategy is unconstrained and when the editing must be produced in a streaming way, i.e. by a letter-to-letter transducer