论文标题
减少测试局部阈值测试性的时间复杂性
Reducing the time complexity of testing for local threshold testability
论文作者
论文摘要
局部阈值可检验的语言L是一种具有属性的语言，对于某些非负整数k和l，对于l的某些单词u，一个v v属于l （1）单词u和v的长度k-1的前缀[后缀]重合， （2）在两个单词u和v中，长度k的每个因素的发生数量均相同或大于L-1。 如果自动机接受某些L和K的局部阈值可检验的语言，则确定性有限自动机可在局部测试。 可以在可局部测试确定性有限自动机进行确定性的有限自动机。根据这些条件，我们修改算法以验证自动机的局部阈值测试性并降低算法的时间复杂性。该算法是作为$ c/c ^{++} $ package testas的一部分实现的。 \ texttt {http://www.cs.biu.ac.il/qumqumquh trakht/testas.html}。
A locally threshold testable language L is a language with the property that for some non negative integers k and l and for some word u from L, a word v belongs to L if and only if (1) the prefixes [suffixes] of length k-1 of words u and v coincide, (2) the numbers of occurrences of every factor of length k in both words u and v are either the same or greater than l-1. A deterministic finite automaton is called locally threshold testable if the automaton accepts a locally threshold testable language for some l and k. New necessary and sufficient conditions for a deterministic finite automaton to be locally threshold testable are found. On the basis of these conditions, we modify the algorithm to verify local threshold testability of the automaton and to reduce the time complexity of the algorithm. The algorithm is implemented as a part of the $C/C ^{++}$ package TESTAS. \texttt{http://www.cs.biu.ac.il/$\sim$trakht/Testas.html}.
