ALGORITHMS VERIFYING LOCAL THRESHOLD AND PIECEWISE TESTABILITY OF SEMIGROUP AND SOLVING ALMEIDA PROBLEM
A. N. Trahtman · 2001
The local threshold (piecewise) testability problem for semigroup is, given asemigroup, to decide, if the semigroup is locally threshold (piecewise) testable or not. We present apolynomial time algorithms of order $O(n^{3}) $ for the local threshold testability problem and of order $O(n^{2}) $ for the piecewise testability problem. These algorithms and some other have been implemented as $C^{++}$ package. New form of necessary and sufficient conditions of local testability is de-scribed. The precise upper bound on the order of local testability is indicated. We give apositive answer on the following problem of Almeida “Is the semigroup pseudovariety $x^{2}=0=xyxzx $ , $xy1,..ykxyk.,.y1=0(k>1) $ decide, able in polynomial time?”