数理解析研究所講究録 1222 巻 2001 年 145-151

145

ALGORITHMS VERIFYING LOCALTHRESHOLD AND PIECEWISE TESTABILITY
OF SEMIGROUP AND SOLVING ALMEIDAPROBLEM
A.N. Trahtman
Bar-Ilan University, Department of Math, and CS, 52900 Ramat Gan, Israele-mail:trakht@macs.biu.ac.il
Abstract
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 described. The precise upper bound on the order of local testability is indicated.
We give apositive answer on the following problem of Almeida “Is thesemigroup pseudovariety $x^{2}=0=xyxzx$ , $xy1,..ykxyk.,.y1=0(k>1)$ decide,
able in polynomial time?”

Keywords: locally threshold testable, piecewise testable, locally testable, sernigroup, algorithm

Introduction
Piecewise testable [8] and localy testable ([7], [3]) languages with generalzations
are the best known subclasses of star-ffee languages. Both these classes define two
important directions in investigations of these languages and corresponding semigroups. The local threshold testability [2] generalizes the concept of local testability.
The local testability can be considered as aspecial case of local -threshold testability
$l$

146
There are polynomial time algorithms for the local testability problem of orderfor finite automata [4] and for finite semigroups [11]. Polynomial time alg0rithms for the local threshold [13] and piecewise [9] testability problems for finite
automata of order $O(n^{5})$ are known too. The last algorithm was modified [14] andhis order was reduced to $O(n^{2})$ .
We present an algorithm for the local threshold testability problem for semigroups. In spite of the fact that we must verify aquasiidentity in five variables,
the time complexity of the algorithm is $O(n^{3})$ . An algorithm of order $O(n^{2})$ for thepiecewise testability problem for semigroups will be presented as well.
Both algorithms are implemented in the package of scientific programs TES. The input of the semigroup programs is aCayley graph of
TAS written in
the semigroup (the table of type: elements on generators) presented as text file.
The maximal size of semigroups we consider on standard personal computer wassome thousands elements with the number of generators about ahalf. For creation
semigroups of great size, we use aprogram of finding direct product of semigroups
presented by their Cayley graph.
We study necessary and sufficient conditions of local testability for semigroup
and add fresh wording of these conditions. The identities of -testable semigroup[10] are used here.
The set of locally threshold testable semigroups forms aquasivariety of semigroups and we present abasis of quasiidentities of the quasivariety.
It will be proved that the precise upper bound on the order of local testability for-element semigroup is equal to . Let us notice that the precise upper bound on
the order of local testability for the state transition graph of deterministic finite
automaton wit $m$ nodes is eqial to 0.5 $(m^{2} -m)$ $+1[12]$ .
Some problems in finite semigroups playing anoticeable role in the study ofrecognizable languages arise in monograph of Almeida [1]. We give apositive answer
on the problem 5from this book.
$O(n^{2})$$C^{++}$

$k$

$n$

$n$

$\Gamma$

Notation and definitions
be an alphabet and let
denote the ffee semigroup on E.
If $w\in F$ , let $|w|$ denote the length of .
Let $h_{k}(w)[t_{k}(w)]$ denote the prefix [suffix] of of length or if $|w|<k$ .
Let $F_{k,j}(w)$ denote the set of factors of of length with at least occurrences.
Asemigroup is called 1-threshold -testable if there is an alphabet [and asurjective morphism :, if $h_{k-1}(u)=h_{k-1}(v)$ ,] such that for all ,$j\leql$$=v\phi$ .
$F_{ki}(u)=F_{k,j}(v)$$t_{k-1}(u)=t_{k-1}(v)$ and, thenfor aU
Asemigroup is locally threshold testable if it is threshold testable forsome and . is called locally testable if $l=1$ .
Let$F=\Sigma^{+}$$\Sigma$

$w$

$k$

$w$

$k$

$w$

$S$

$w$

$j$

$\Sigma$$\mathrm{k}$$\phi$$\Sigma^{+}arrow S$$u$$v\in\Sigma^{+}$$u\phi$

$S$

$k$

$l$

$S$

$l$

$k$

147
The semigroup is piecewise testable if and only if the ideals generated by
distinct elements are distinct [8].
Asemigroupnon-trivial subgroups is called aperiodic.
Let be abinary relation on semigroup such that for $a,b\in Sapb$ iff for some
idempotent $e\in Sae=a$ , $be=b$ .
Let Abe abinary relation on such that for , $b\in Sapb$ iff for some idempotent$e\in Sea=a$ , $eb=b$ .
The unary operation
assigns to every element of afinite semigroup theunique idempotent ffom the subsemigroup generated by .
Pseudovariety of finite semigroups is aset of finite semigroups closed underfinitary direct products, homomorphic images and subsemigroups.
Quasivariety of semigroups is aset of semigroups closed under direct products
and subsemigroups.
$S$$\dot{\mathrm{w}}\mathrm{i}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{u}\mathrm{t}$$S$$\rho$$S$$a$$x^{w}$

$S$

$x$

$x$

1Local testability
The best known description of necessary and sufficient conditions of local testability was found independently by Brzozowski and Simon [3], McNaughton [6] andZalcstein [15] :finite semigroup is locffiy testable iff its subsemigroup $eSe$ is commutative andidempotent for any idempotent $e\in S$ .
We give here extended form and new wording of necessary and sufficient conditions of local testability of semigroup.
$S$

Theorem 1.1
finite semigroup , the following four conditions are equivalent:1) is locally testable.
$2)eSe$ is 1-testable for every idempotent $e\in S(eSe$ is commutative and idealstent).
3) Se [eS] is 2-testable for every idempotent $e\in S$ .
4) SeS is 2-testable for every idempotent $e\in S$ .
$S$

$S$

Proof. Equivalency of 1) and 2) is proved in [15].
$3)arrow 2)$ . Se satisfies identities of 2-testability: $xyx=xyxyx,x^{2}=x^{3}$ ,xyxzx
xzxyx [10], whence $ese=eseese$ and eseete $=eteese$ for any idempotent $e\in S$ andfor any , $t\in S$ . Therefore $eSe$ is commutative and idempotent.
$2)arrow 4)$ Identities of 1-testability in $eSe$ may be presented in the following form
, exeyefor arbitrary $x,y\in S$ . Therefore for any $u,v,w$ divided by we have,, uvuwu
So identities of 2-testability are vald in SeS.
$4)arrow 3)$ $Se\subseteq SeS$ , whence identities SeS are vald in Se.
$=$

$s$

$\mathrm{e}\mathrm{x}\mathrm{e}=\mathrm{e}\mathrm{x}\mathrm{e}\mathrm{x}\mathrm{e}$$=\mathrm{e}\mathrm{y}\mathrm{e}\mathrm{x}\mathrm{e}$$e$$\mathrm{u}\mathrm{u}=\mathrm{u}\mathrm{u}\mathrm{u}$$\mathrm{u}\mathrm{v}\mathrm{u}=\mathrm{u}\mathrm{v}\mathrm{u}\mathrm{v}\mathrm{u}$$=\mathrm{u}\mathrm{w}\mathrm{u}\mathrm{v}\mathrm{u}$148
Theorem 1.2 The precise upper bound on the order of local testability for a locally.
testable finite semigroup is equal to
Proof. Every -testable semigroup is $(n-1)$ -nilpotent extension of 2-testablesemigroup [10]. $(n-1)$ -nilpotent extension of any semigroup has size not less than .
is an upper bound on the order of local testability. This
Therefore
upper bound is reached in cyclic -element semigroup without non-trivial subgroups
because in this semigroup identities of -testability[10] are valid and the identities
of $(n-1)$ -testability are not valid.
$S$

$|S|$

$S$

$n$

$n$

$n\leq|S|\mathrm{a}\mathrm{n}\mathrm{d}.|S|$

$n$

$n$

2Background of algorithms
We can formulate the result of Beauquier and Pin [2] in the following form:
Theorem 2.1 [ A language is locally threshold testable if and only if the syntactic semigroup of is aperiodic and for any two idempotents , and elements, , of we have$L$$\eta$

$S$

$a$

$u$

$b$

$L$

$e$

$f$

$S$

$eafilebf=ebfueaf$

Syntactic semigroups of finite automata are finite. Therefore we have
Corollary 2.2 The set of locally threshold testable semigroups forms the set offinite semigroups from a quasivariety defined by quasiidentities$x^{2}=x$ , $y^{2}=yarrow xuyvxty$ $=xtyvxuy$$x^{n}x^{m}=x^{\mathfrak{n}}arrow x^{n}x=x^{n}(n, m\in N)$

Lemma 2.3 Elements $s,t$ from belong to some subsemigroup such that $A=$.
and if and only if $spt$ and$eSf$ for some idempotents
The proof follows from the definitions of and A.
Theorem 2.4 A language is locally threshold testable if and only if the syntactic
semigroup of is aperiodic and for any three elements , , of such that $spt$
and
we have
$A$

$S$

$f$

$e$

$\mathrm{s}\mathrm{X}\mathrm{t}$$\rho$

$L$

$S$

$L$

$s$

$u$

$S$

$t$

$s\lambda t$$sut=tus$

The proof follows from theorem 2.1 and lemma 2.3.
The following result is due to Simon [8]:Theorem 2.5 [8] Finite semigroup is pieceeuise testable iff
for any teuo elements , $y\in S$ holds
$S$

$x$

$(xy).x$ $=y(xy)$.

$=(xy)$.

$S$

is aperiodic andObvious is the following
Lemma 2.6 A finite semigroup is aperiodic if and only if for any $s\in S$ there
exists an integer such that $s^{k}=s^{k+1}$ . For such , we have $s^{w}=s^{k}=s^{k+1}$ .
$S$

$k$

$k$

149
3Algorithms
Let , :be elements of semigroup , $n=|S|$ .
Local threshold testability. The algorithm is based on the theorem 2.4.
$s$$\bullet$

$S$

$s$

For any $s\in S$ let us find ?. We consider the sequence , , ,verify the condition $s^{:}=s^{:+1}$ . If the condition is not valid for some$i\leq n$ then the semigroupis not localy threshold testable.
$s$$s^{2}$

andand all$s^{:},\ldots s^{n}$$\ldots$$s$$S$$\bullet$Let us form abinary square table $L[R]$ of the size in the folowing way:
For any $i,j\leq n$ suppose $L_{:,j}=1[R_{j}.,=1]$ if there exists an idempotent$e\in S$ such that$es:=s$ :and $es_{j}=s_{j}$ [ $s:e=S$:and $s_{j}e=s_{j}$ ]. In opposite$L_{:,j}=0[R_{j}.,=0]$case. The table presents the binary relation Aon andthe table R-p. Both these considered steps have order $O(n^{3})$ .
Let us find the intersection
and form acorresponding binary square table.
$n$

$L$

$S$

$\mathrm{p}\mathrm{d}\mathrm{X}$$\bullet$, , $s_{k}\in S$ where, let us check the condition$s:s_{k}s_{j}=s_{j}s_{k}s:$ . The valdity of the condition for any triple of elements implies
local threshold testability of . In opposite case is not locally thresholdtestable.
For any triple$S:$$S:(\rho\cap\lambda)s_{j}$$s_{j}$$S$$S$

The step has order $O(n^{3})$ .

2.6.

Piecewise testability. The algorithm is based on the theorem 2.5 and lemma$\bullet$

For any $s\in S$ let us find . . We consider the sequence , , ,. The
idempotent
is equal to such that $s^{:}=s^{:+1}$ . If does not exist then thesemigroup is not piecewise testable.
$s^{\omega}$$s^{*}$$s^{\omega}$$s$$s^{2}$$s^{:},\ldots s^{\mathfrak{n}}$$\ldots$$s^{\omega}$$S$

For given element , the step is linear in the size of semigroup.
$s$$\bullet$

For any pair , $t\in S$ , let us check the condition $(st)^{\omega}s=t(st)^{d}‘=(st).$ .The
validity of the condition for any pair of elements implies piecewise testabilityof . In opposite case is not piecewise testable.
$s$

$S$

$S$

The step has order $O(n^{2})$ .
The algorithm to verify the local threshold testability of the semigroup has order$O(n^{3})$ and the algorithm to verify the piecewise testability ofhas order $O(n^{2})$ .
$S$

$S$

150
4Solution of Almeida problem
We consider the following problem 5ffom the monograph of Almeida [1]:“Is the semigroup pseudovariety defined by identities$x^{2}=0=xyxzx,xy_{1}\ldots y_{k}xy_{k}\ldots y_{1}$$=0(k>1)$

decidable in polynomial time?”
Let us present an algorithm for checking this condition for the given n-element
semigroup . We shall consider abinary relation on $S:apb$ for , $b\in S$ if for some$c\in S$ holds $a=cbc$$S$$\bullet$$\bullet$$a$$\rho$

Check the identities $x^{2}=0=xyxzx$ .
For any , $c\in S$ , suppose $b\rho cbc$
So we define the relation and let us find the transitive closure of the relation. For this aim, we consider adirected graph with nodes from where $aarrow b$
.
iff
$b$

$\overline{\rho}$$\rho$$S$$\rho$$\mathrm{a}\mathrm{p}\mathrm{b}$$\bullet$for any node$a$-let us mark aU nodes such thatby the label 1.
-for any node marked by 1, let us mark all nodes such that $xpb$ bylabel 2.
The process goes until there are edges with marked beginning and nonmarked end.
-now
if the node is labeled by some label andif the nodeis labeled by the label 2.
-for any such that(labeled bylabel 2) let us check the condition$abab=0$ . If the condition does not hold the algorithm stops and theanswer for considered semigroup is negative.
$b$$a\rho b$

$b$

$x$

$b$

$a\overline{\rho}b$

$b$

$b$

$a\overline{\rho}^{2}b$$a\overline{\rho}^{2}b$the answer for considered semigroup is positive.
Theorem 4.1 For any , $b\in S$ ,iff$(k>1)$ . The considered algorithm has the order $O(n^{3})$ where$\bullet$$a$$a\overline{\rho}^{2}b$$a=c_{1}\ldots c_{k}bc_{k}\ldots c_{1}$$n$for some$c_{1}$,$\ldots$,$c_{k}$

is the size of .
$S$

Proof. According the definition, $apb$ iff for some holds $b=cac$ . Therefore,
and
iff for some , ,apb iff for some , , we havewhere $k>1$ .
This checking identities $x^{2}=0=xyxzx$ needs at most $n^{3}+n^{2}$ steps.
The process of labeling nodes for given node is linear in the number of edgesof the graph because every edge is considered at most once. There areedges in$abab=0$
the worst case. Checking the condition
for given is linear in the size ofsemigroup.
So the process of labeling nodes and checking conditions needs at most steps.
$c$$c_{1}$$\ldots$$c_{k}$$b=c_{1}\ldots c_{k}ac_{k}\ldots c_{1}$$a\overline{\rho}^{2}b$$c_{1}$$b=c_{1}\ldots c_{k}ac_{k}\ldots c_{l}$$a$$n^{2}$$a$$n^{3}$$\ldots$$c_{k}$

151
References[1] J. Almeida, Finite Semigroups and Universal Algebra, Series in Algebra, World
Sci., Vol. 3, 1995.
[2] D. Beauquier, J.E. Pin, Factors of words, Lect. Notes in Comp. Sci, Springer,
Berlin, 372(1989), 63-79.
[3] J.A. Brzozowski, I. Simon, Characterizations of locally testable events, Discrete
Math., 4, (1973), 243-271.

[4] S. Kim, R. McNaughton, R. McCloskey, Apolynomial time algorithm for the
local testability problem of deterministic finite automata, IEEE Trans. Comput.
40(1991) N1O, 1087-1093.
[5] G. Lallement, Semigroups and combinatorial applications, Wiley, N.Y., 1979.

[6] R. McNaughton, Algebraic decision
Math.Syst.Tthery, 8( 1974), 60-76.

procedure

forlocal testability,[7] R. McNaughton, S. Papert, Counter-free automata, M.I.T. Press Mass., 1971.
[8] I. Simon, Piecewise testable events, Springer, Lect. Notes in Comp. Sci.,
33(1975), 214-222.

[9] J. Stern, Complexity of some problems from the theory of automata. Inf. andControl, 66(1985), 163-176.
[10] A.N. Trahtman, Identities of locally testable semigroups. Comm. in Algebra, v.
27, 11(1999), 5405-5412.
[11] A.N. Trahtman, Apolynomial time algorithm for local testability and its level,, No. 1(1998), 31-39.
Int. J. of Alg. and Comp.,$\mathrm{v}\mathrm{o}\mathrm{l}(9)$[12] A.N. Trahtman, Aprecise estimation of the order of local testability of adeterministic finite automaton, Springer, Lect. Notes in Comp. Sci., 1436(1998),

198-212.
[13] A.N. Trahtman, An algorithm to verify local threshold testability of deterministic finite automata. WIA99, Potsdam, Germany, July 17-20, 1999.

[14] A.N. Trahtman, Ver .ng piecewise testability of finite deterministic automata.
CIAA2000, London, Ontario, Canada, July 24-25, 2000.
$.\infty$[15] Y. Zalcstein, Locally testable semigroups, Semigroup Forum, $5(1973)$ , 216-227