A polynomial time algorithm for the local testability problem of deterministic finite automata
Sung-Hwan Kim, Robert McNaughton, Robert McCloskey · IEEE Transactions on Computers · 1991
The local testability problem of deterministic finite automata is investigated. A locally testable language is a language with the property that, for some nonnegative integer k, whether or not a word w is in the language depends on (1) the prefix and suffix of w of length k, and (2) the set of substrings of w length k+1, without regard to the order in which these substrings occur. The local testability problem is, given a deterministic finite automation, to decide whether or not it accepts a locally testable language. The authors present an O(n/sup 2/) time algorithm for the local testability problem based on two simple properties that characterize locally testable automata.>