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.
bounded repair regular languages edit distance