Bounded repairability of word languages
作者：
Highlights：
• 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.
摘要
•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,Edit distance,Regular languages
论文评审过程：Received 14 February 2012, Revised 7 March 2013, Accepted 10 June 2013, Available online 1 July 2013.
论文官网地址：https://doi.org/10.1016/j.jcss.2013.06.001
