Bounded repairability of word languages

• We formalize the bounded repair problem and characterize when regular languages admit bounded repair, for streaming and non-streaming settings.
• We show that bounded repairability in the streamingsetting is independent of the lookahead and is robust under different cost functions.
• Using the characterizations above, we give results on the complexity of the bounded repair problem in each setting.
• We study the complexity of computing the optimal number of edits and the optimal repair strategy in the streaming setting.
• We demonstrate special cases where the streaming and non-streaming bounded repair problems have the same solution.

What do you do if a computational object (e.g. program trace) fails a specification? An obvious approach is to perform a repair: modify the object minimally to get something that satisfies the constraints. This approach has been investigated 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 language. 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.