- [1]
- A.N. Trahtman, A polynomial time algorithm for local testability
and its level.
*Int. J. of Alg. and Comp.*v. 9,**1**(1998), 31-39. - [2]
- A.N. Trahtman, Algorithms finding the order of local testability of deterministic finite automaton and estimation of the order, Th. Comp. Sci., 235(2000), 183-204.
- [3]
- A.N. Trahtman, Piecewise and local threshold testability of DFA. Lect. Notes in Comp. Sci., 2138(2001), 347-358.

A locally testable language *L* is a language with the property that for
some nonnegative integer *k*, called the order or the level of local
testability, 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*.
Local testablility has a wide spectrum of applications. For instance,
regular languages and picture languages can be described with help of a strictly
locally testable languages.
The locally threshold testable languages generalize the concept of
locally testable language.
A language is piecewise testable iff its syntactic monoid is
*J*-trivial (meaning that distinct elements of monoid generate distinct ideals).

We implement a set of procedures for deciding whether or not a language
given by its minimal automaton or by its syntactic semigroup
is locally testable, threshold locally testable, strictly locally
testable, or piecewise testable. The level of local testability is also found.
Some new effective polynomial time algorithms have been implemented as
C ^{++} package (TESTAS).
The input of the semigroup algorithms is Cayley graph of the semigroup.

The time complexity of algorithm for local testability problem
and piecewise testability problem
of automaton and of syntactic semigroup of the language and
for finding the order of local testability for syntactic semigroups
is O(*n*^{2}) [1], [3].
The time complexity of algorithm for the local threshold testability
problem for syntactic semigroup of the language is O(*n*^{3})
and for automaton of the language is O(*n*^{5}) [3].
We implement in our package
a polynomial time algorithm of worst case asymptotic cost O(*n*^{2}) for
finding the bounds on order of local testability for a given transition graph
of the automaton [2] and
a polynomial time algorithm of worst case asymptotic cost O(*n*^{3}) for
checking the 2-testability [2].
Checking the *k*-testability for fixed *k* is polynomial but growing with *k*.
For checking the *k*-testability [2], we use
an algorithm of worst case asymptotic cost O(*n*^{k-1}).
The order of the last algorithm is growing with *k* and so
we have non-polynomial algorithm for finding the order of
local testability.

Sponsored in part by the FCT approved
projects POCTI 32817/99 and POCTI/MAT/37670/2001 in participation with
the European Community Fund FEDER and by FCT through *Centro de Matemática
da Universidade do Porto.* Also sponsored in part by FCT, the
*Faculdade de Ciências da Universidade do Porto, Programa Operacional Ciência, Tecnologia, Inovação do Quadro Comunitário de Apoio III*, and by *Caixa Geral de Depósitos*.

File translated from T

On 4 Apr 2002, 17:46.