论文标题
精确估计确定性有限自动机的局部可检验性顺序
Precise estimation on the order of local testability of deterministic finite automaton
论文作者
论文摘要
可以局部测试的语言L是一种具有属性的语言，该语言对于某些非负整数K（称为局部测试的顺序或局部测试级别），无论是语言中的单词u是否取决于（1）（1）长度为k-1的前缀和后缀k-1和（2）单词u的长度k的中间部分s组。对于给定的K，该语言称为k检验。我们为自动机的语言提供了必要和充分的条件，可以按照相关图的路径长度来k检验。从这些结果中遵循了对上限和可检测顺序的下限的一些估计。我们改善了局部可测试的确定性有限自动机的可测试顺序，n状态为n（n-2）+1 这是最好的。我们对Kim，McNaughton和Mac-Closkey的以下猜想给出了一个答案，以确定有限的局部可在n个州进行本地测试的自动机：\当字母大小为两个时，局部可测试的顺序不超过n的功率1.5？”我们的答案是负数。
A locally testable language L is a language with the property that for some non negative integer k, called the order or the level of local testable, whether or not a word u in the language L depends on (1) the prefix and the suffix of the word u of length k-1 and (2) the set of intermediate partial strings of length k of the word u. For given k the language is called k-testable. We give necessary and sufficient conditions for the language of an automaton to be k-testable in the terms of the length of paths of a related graph. Some estimations of the upper and of the lower bound of testable order follow from these results. We improve the upper bound on the testable order of locally testable deterministic finite automaton with n states to n(n-2)+1 This bound is the best possible. We give an answer on the following conjecture of Kim, McNaughton and Mac-CLoskey for deterministic finite locally testable automaton with n states: \Is the local testable order of no greater than n in power 1.5 when the alphabet size is two?" Our answer is negative. In the case of size two the situation is the same as in general case.
