  A locally threshold testable language L is a language with the property that
for some non negative integers k and l, whether or not a word u is in the
language L depends on (1) the prefix and suffix of the word u of length k > 1
and (2) the set of intermediate substrings of length k of the word u where the
sets of substrings occurring at least j times are the same, for j <= L. For
given k and L the language is called l-threshold k-testable. A finite
deterministic automaton is called l-threshold k-testable if the automaton
accepts a l-threshold k-testable language. In this paper, the necessary and
sufficient conditions for an automaton to be locally threshold testable are
found. We introduce the first polynomial time algorithm to verify local
threshold testability of the automaton based on this characterization. New
version of polynomial time algorithm to verify the local testability will be
presented too.
