You are not logged in to this journal. Log in

A locally testable language is a language with the property that, for some positive integer $j$, whether or not a string $x$ is in the language depends on (1) the prefix and suffix of $x$ of length $j - 1$, and (2) the set of substrings of $x$ of length $j$, without regard to the order in which these substrings occur or the number of times each substring occurs. For any $j$ for which this is true, it is said that the language is $j$ -testable For a given locally testable language, the smallest such number $j$ is called the order of the language. Locally testable languages are regular and therefore these concepts apply to the finite automata that recognize the languages. The authors show that computing the order of a given locally testable deterministic automaton is NP-hard and present a polynomial-time $ \epsilon $-approximation algorithm for computing it. In addition, an upper bound of $2n^2 + 1$ on the order of a locally testable automaton of $n$ states is obtained, and the co-NP-completeness of the problem of whether, for a given $j$, a given deterministic automaton is $j$ -testable is proven. ©1994 Society for Industrial and Applied Mathematics