  A locally testable semigroup S is a semigroup with the property that for some
nonnegative integer k, called the order or level of local testability, two
words u and v in some set of generators for semigroup S are equal in the
semigroup if (1) the prefix and suffix of the words of length k coincide, and
(2) the set of intermediate substrings of length k of the words coincide. The
local testability problem for semigroups is, given a finite semigroup, to
decide, if the semigroup is locally testable or not. Recently, we introduced a
polynomial time algorithm for the local testability problem and to find the
level of local testability for semigroups based on our previous description of
identities of $k$-testable semigroups and the structure of locally testable
semigroups. The first part of the algorithm we introduce solves the local
testability problem. The second part of the algorithm finds the order of local
testability of a semigroup. The algorithm is of quadratic order where n is the
order of the semigroup.
