论文标题
左[右]局部可检验性的多项式时间算法
Polynomial time algorithm for left [right] local testability
论文作者
论文摘要
右[左]可在本地测试的语言S是一种具有属性的语言，对于某些非负整数k，字母内的两个单词u和v在半组中是相等的，如果（1）（1）长度k重合的前缀和后缀，（2）单词长度的k effirence k y the of the of the of the of the Segince s segix in of First Fifffixs [）我们为确定性有限自动机的图形[半群]提供了必要的条件[半组]为过渡图[半组]，该图形接受右[左]可在本地测试的语言，并且具有局部IDEMPOTENT SEMI组的确定性有限自动机的过渡图的必要条件。我们根据这些条件为确定性有限自动机的过渡半组的右[左]局部可测试问题引入了多项式时间算法。多项式时间算法用局部基础过渡半组验证自动机的过渡图。
A right [left] locally testable language S is a language with the property that for some non negative integer k two words u and v in alphabet S are equal in the semi group if (1) the prefix and suffix of the words of length k coincide, (2) the set of segments of length k of the words as well as 3) the order of the first appearance of these segments in prefixes [suffixes] coincide. We present necessary and sufficient condition for graph [semi group] to be transition graph [semi group] of the deterministic finite automaton that accepts right [left] locally testable language and necessary and sufficient condition for transition graph of the deterministic finite automaton with locally idempotent semi group. We introduced polynomial time algorithms for the right [left] local testable problem for transition semi group and transition graph of the deterministic finite automaton based on these conditions. Polynomial time algorithm verifies transition graph of automaton with locally idempotent transition semi group.
