Correcting Counter-Automaton-Recognizable Languages
Correcting Counter-Automaton-Recognizable Languages
复制标题
纠正反自动机可识别的语言
DOI：
10.1137/0207029
复制
发表时间：
1978
期刊：
影响因子：
--
通讯作者：
J. Seiferas
中科院分区：
文献类型：
--
作者：
R. Wagner;J. Seiferas
将字符串 x 纠正为语言 L 是找到字符串 $y \in L$ 的问题，其中 x 可以以最少的成本编辑。这里考虑的编辑操作是单字符删除、单字符插入和单字符替换，每个操作都有独立的成本，不依赖于上下文。采用线性时间算法解决单源图最短距离问题，展示了如何在具有单位操作成本函数的 RAM 上以与 $n^2$ 成比例的时间将长度为 n 的字符串纠正为计数器自动机接受的语言。该算法是统一的柜台自动机和编辑成本函数；并且显示了校正时间如何取决于自动机的大小、成本函数的性质以及校正成本本身。对于不太一般的情况，描述了可能更快的算法，包括线性时间算法，用于需要很少校正并且自动机的计数器活动由...确定的情况。
Correction of a string x into a language L is the problem of finding a string $y \in L$ to which x can be edited at least cost. The edit operations considered here are single-character deletions, single-character insertions, and single-character substitutions, each at an independent cost that does not depend on context. Employing a linear-time algorithm for solving single-origin graph shortest distance problems, it is shown how to correct a string of length n into the language accepted by a counter automaton in time proportional to $n^2 $ on a RAM with unit operation cost function. The algorithm is uniform over counter automata and edit cost functions; and it is shown how the correction time depends on the size of the automaton, the nature of the cost function, and the correction cost itself. For less general cases, potentially faster algorithms are described, including a linear-time algorithm for the case that very little correction is necessary and that the automaton’s counter activity is determined by ...