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(n2) [1], [3]. The time complexity of algorithm for the local threshold testability problem for syntactic semigroup of the language is O(n3) and for automaton of the language is O(n5) [3]. We implement in our package a polynomial time algorithm of worst case asymptotic cost O(n2) 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(n3) 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(nk-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.