论文标题
用于局部可检验性及其水平的多项式时间算法
A polynomial time algorithm for local testability and its level
论文作者
论文摘要
局部可测试的半群S是具有该特性的半群，对于某些非负整数K，称为局部可检验性的顺序或级别，在某些半群中，在某些发电机中，在（1）长度k偶然的单词的前缀和（2）中间词的coince konemimed s sovine coince keinds coince keinds coince kinemogroup中的两个单词u和v是平等的。对于半群的局部可检验性问题，给出了有限的半群，以确定半群是否可以在本地测试。最近，我们根据我们先前对$ k $ testable的半群的身份的描述以及本地可测试的半群的结构，为局部可检验性问题引入了多项式时间算法，并找到了半群的局部测试性水平。我们引入的算法的第一部分解决了局部可检验性问题。该算法的第二部分找到了半群的局部可检测性顺序。该算法是二次顺序，其中n是半群的顺序。
A locally testable semigroup S is a semigroup with the property that for some nonnegative integer k, called the order or level of local testability, two words u and v in some set of generators for semigroup S are equal in the semigroup if (1) the prefix and suffix of the words of length k coincide, and (2) the set of intermediate substrings of length k of the words coincide. The local testability problem for semigroups is, given a finite semigroup, to decide, if the semigroup is locally testable or not. Recently, we introduced a polynomial time algorithm for the local testability problem and to find the level of local testability for semigroups based on our previous description of identities of $k$-testable semigroups and the structure of locally testable semigroups. The first part of the algorithm we introduce solves the local testability problem. The second part of the algorithm finds the order of local testability of a semigroup. The algorithm is of quadratic order where n is the order of the semigroup.
