%Reduction des tores \documentstyle[11pt]{article} \pagestyle{plain} \oddsidemargin 0 cm \evensidemargin 2 cm \textwidth 16 cm \topmargin 0 cm \textheight 24 cm \renewcommand{\baselinestretch}{1.9} \title{ALGORITHMS VERIFYING LOCAL THRESHOLD AND PIECEWISE TESTABILITY OF SEMIGROUP AND SOLVING ALMEIDA PROBLEM} \date{} \author{A.N. Trahtman} %\theoremstyle{plain} \newtheorem{defn}{D\'efinition}[section] \newtheorem{quest}[defn]{Question} \newtheorem{prop}[defn]{Proposition} \newtheorem{thm}[defn]{Theorem} \newtheorem{lem}[defn]{Lemma} \newtheorem{cor}[defn]{Corollary} %\theoremstyle{definition} \begin{document} \maketitle Bar-Ilan University, Department of Math. and CS, 52900 Ramat Gan, Israel e-mail: trakht@macs.biu.ac.il \begin{abstract} The local threshold (piecewise) testability problem for semigroup is, given a semigroup, to decide, if the semigroup is locally threshold (piecewise) testable or not. We present a polynomial 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 a positive answer on the following problem of Almeida "Is the semigroup pseudovariety $x^2=0=xyxzx, xy_1...y_kxy_k...y_1=0 (k>1)$ decidable in polynomial time? \end{abstract} Keywords: {\it locally threshold testable, piecewise testable, locally testable, semigroup, algorithm} \section*{Introduction} Piecewise testable $\cite {Si}$ and locally testable ($\cite {MP}$, $\cite {BS}$) languages with generalizationsare most known subclasses of star-free languages. Both these classes define two important directions in investigations of these languages and corresponding semigroups. The local threshold testability $\cite {BP}$ generalizes the concept of local testability. The local testability can be considered as a special case of local $l$-threshold testability for $l=1$. There are polynomial time algorithms for the local testability problem of order $O(n^2)$ for finite automata $\cite {K91}$ and for finite semigroups $\cite {Tc}$. Polynomial time algorithms for the local threshold $\cite {TG}$ and piecewise $\cite {St}$ testability problems for finite automata of order $O(n^5)$ are known too. The last algorithm was modified $\cite {T4}$ and his 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 a quasiidentity in five variables, the time complexity of the algorithm is $O(n^3)$. An algorithm of order $O(n^2)$ for the piecewise testability problem for semigroups will be presented as well. Both algorithms are implemented in the package of scientific programs TESTAS written in $C^{++}$. The input of the semigroup programs is a Cayley graph of the semigroup (the table of type: elements on generators) presented as text file. The maximal size of semigroups we consider on standard personal computer was some thousands elements with the number of generators about a half. For creation semigroups of great size, we use a program 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 $k$-testable semigroup $\cite {Tr}$ are used here. The set of locally threshold testable semigroups forms a quasivariety of semigroups and we present a basis of quasiidentities of the quasivariety. It will be proved that the precise upper bound on the order of local testability for $n$-element semigroup is equal to $n$. Let us notice that the precise upper bound on the order of local testability for for the state transition graph $\Gamma$ of deterministic finite automaton wit $m$ nodes is eqial to $0.5(m^2-m)+1$ $\cite {Te}$. Some problems in finite semigroups playing a noticeable role in the study of recognizable languages arise in monograph of Almeida $\cite {Al}$. We give a positive answer on the problem 5 from this book. \section*{Notation and definitions} Let $\Sigma$ be an alphabet and let $F=\Sigma^+$ denote the free semigroup on $\Sigma$. If $w \in F$, let $|w|$ denote the length of $w$. Let $h_k(w)$ $[t_k(w)]$ denote the prefix [suffix] of $w$ of length $k$ or $w$ if $|w| < k$. Let $F_{k,j}(w)$ denote the set of factors of $w$ of length $k$ with at least $j$ occurrences. A semigroup $S$ is called {\bf l-threshold k-testable} if there is an alphabet $\Sigma$ [and a surjective morphism $\phi : \Sigma^+ \to S$] such that for all $u$, $v \in \Sigma^+$, if $h_{k-1}(u)=h_{k-1}(v)$, $t_{k-1}(u)=t_{k-1}(v)$ and $F_{k,j}(u)=F_{k,j}(v)$ for all $j \le l$, then $u\phi = v\phi$. A semigroup $S$ is {\bf locally threshold testable} if it is $l$-threshold $k$-testable for some $k$ and $l$. $S$ is called {\bf locally testable} if $l=1$. The semigroup $S$ is {\bf piecewise testable} if and only if the ideals generated by distinct elements are distinct $\cite {Si}$. A semigroup without non-trivial subgroups is called {\bf aperiodic}. Let $\rho$ be a binary relation on semigroup $S$ such that for $a,b \in S$ $a \rho b$ iff for some idempotent $e \in S$ $ae=be$. Let $\lambda$ be a binary relation on $S$ such that for $a,b \in S$ $a \lambda b$ iff for some idempotent $e \in S$ $ea=eb$. The unary operation $x^{\omega}$ assigns to every element $x$ of a finite semigroup $S$ the unique idempotent from the subsemigroup generated by $x$. Pseudovariety of finite semigroups is a set of finite semigroups closed under finitary direct products, homomorphic images and subsemigroups. Quasivariety of semigroups is a set of semigroups closed under direct products and subsemigroups. \section {Local testability} The best known description of necessary and sufficient conditions of local testability was found independently by Brzozowski and Simon $\cite {BS}$, McNaughton $\cite {M}$ and Zalcstein $\cite {Z}$: finite semigroup $S$ is locally testable iff its subsemigroup $eSe$ is commutative and idempotent for any idempotent $e \in S$. We give here extended form and new wording of necessary and sufficient conditions of local testability of semigroup. \begin{thm} $\label {l.1}$ For finite semigroup $S$, the following four conditions are equivalent: 1) $S$ is locally testable. 2)$eSe$ is 1-testable for every idempotent $e \in S$ ($eSe$ is commutative and idempotent). 3) $Se$ [$eS$] is 2-testable for every idempotent $e \in S$. 4) $SeS$ is 2-testable for every idempotent $e \in S$. \end{thm} Proof. Equivalency of 1) and 2) is proved in $\cite {Z}$. 3) $\to$ 2). $Se$ satisfies identities of 2-testability: $ xyx=xyxyx, x^2=x^3, xyxzx=xzxyx$ $\cite {Tr}$, whence $esee=eseesee$ and $eseetee=eteesee$ for any idempotent $e \in S$ and for any $s,t \in S$. Therefore $eSe$ is commutative and idempotent. 2) $\to$ 4) Identities of 1-testability in $eSe$ may be presented in the following form \centerline{ exe=exexe, exeye=eyexe} for arbitrary $x,y \in S$. Therefore for any $u,v,w$ divided by $e$ we have \centerline{uu=uuu, uvu=uvuvu, uvuwu=uwuvu} So identities of 2-testability are valid in $SeS$. \begin{thm} $\label {l.2}$ The precise upper bound on the order of local testability for a locally testable finite semigroup $S$ is equal to $|S|$. \end{thm} Proof. Every locally testable $n$-element semigroup is ($n-1$)-nilpotent extension of 2-testable semigroup $\cite {Tr}$. Therefore $n$ is an upper bound on the order of local testability. This upper bound is reached in cyclic semigroup without non-trivial subgroups because in such $n$-element semigroup identities of $n$-testability $\cite {Tr}$ are valid and the identities of $(n-1)$-testability are not valid. \section { Background of algorithms} We can formulate the result of Beauquier and Pin $\cite {BP}$ in the following form: \begin{thm} $\label {1.0}$ $\cite {BP}$ A language $L$ is locally threshold testable if and only if the syntactic semigroup $S$ of $L$ is aperiodic and for any two idempotents $e$, $f$ and elements $a$, $u$, $b$ of $S$ we have \centerline{eafuebf=ebfueaf} \end{thm} Syntactic semigroups of finite automata are finite. Therefore we have \begin{cor} $\label {1.c}$ The set of locally threshold testable semigroups forms the set of finite semigroups from a quasivariety defined by quasiidentities \centerline{$x^2=x, y^2=y \to xuyvxty=xtyvxuy$} \centerline{ $x^nx^m=x^n \to x^nx=x^n $ ($n$, $m\in N$)}. \end{cor} \begin{lem} $\label {1.1}$. Elements $s,t$ from $S$ belong to some subsemigroup $A$ such that $A=eSf$ for some idempotents $e$ and $f$ if and only if $s \rho t$ and $s \lambda t$. \end{lem} The proof follows from the definitions of $\rho$ and $\lambda$. \begin{thm} $\label {1.2}$ A language $L$ is locally threshold testable if and only if the syntactic semigroup $S$ of $L$ is aperiodic and for any three elements $s$, $u$, $t$ of $S$ such that $s \rho t$ and $s \lambda t$ we have \centerline{ sut=tus} \end{thm} The proof follows from theorem $\ref {1.0}$ and lemma $\ref {1.1}$. \medskip The following result is due to Simon $\cite {Si}$: \begin{thm} $\label {0.0}$ $\cite {Si}$ Finite semigroup $S$ is piecewise testable iff $S$ is aperiodic and for any two elements $x$, $y \in S$ holds \centerline{$(xy)^{\omega}x=y(xy)^{\omega}=(xy)^{\omega}$} \end{thm} Obvious is the following \begin{lem} $\label {0.1}$ A finite semigroup $S$ is aperiodic if and only if for any $s \in S$ there exists an integer $k$ such that $s^k=s^{k+1}$. For such $k$, we have $s^{\omega}=s^k=s^{k+1}$. \end{lem} \section{Algorithms} Let $s, s_i$ be elements of semigroup $S$, $n=|S|$. {\bf Local threshold testability}. The algorithm is based on the theorem $\ref {1.2}$. \begin{itemize} \item For any $s \in S$ let us find $s^{\omega}$. We consider the sequence $s$, $s^2$, ..., $s^i$,...$s^{n}$ and verify the condition $s^i=s^{i+1}$. If the condition is not valid for some $s$ and all $i \le n$ then the semigroup $S$ is not locally threshold testable. \item Let us form a binary square table $L$ [$R$] of the size $n$ in the following way: For any $i,j \le n$ suppose $L_{i,j}=1$ [ $R_{i,j}=1$] if there exists an idempotent $ \in S$ such that $es_i=es_j$ [ $s_ie=s_je$]. In opposite case $L_{i,j}=0$ [ $R_{i,j}=0$]. The table $L$ presents the binary relation $\lambda$ on $S$ and the table $R$ - $\rho$. Both these considered steps have order $O(n^3)$. Let us find the intersection $\rho \cap \lambda$ and form a corresponding binary square table. \item For any triple $s_i, s_j, s_k \in S$ where $s_i (\rho \cap \lambda) s_j$, let us check the condition $s_is_ks_j=s_js_ks_i$. The validity of the condition for any triple of elements implies local threshold testability of $S$. In opposite case $S$ is not locally threshold testable. The step has order $O(n^3)$. \end{itemize} \medskip {\bf Piecewise testability}. The algorithm is based on the theorem $\ref {0.0}$ and lemma $\ref {0.1}$. \begin{itemize} \item For any $s \in S$ let us find $s^{\omega}$. We consider the sequence $s$, $s^2$, ..., $s^i$,...$s^{n}$. The idempotent $s^{\omega}$ is equal to $s^i$ such that $s^i=s^{i+1}$. If $s^{\omega}$ does not exist then the semigroup $S$ is not piecewise testable. For given element $s$, the step is linear in the size of semigroup. \item For any pair $s,t \in S$, let us check the condition $(st)^{\omega}s=t(st)^{\omega}=(st)^{\omega}$. The validity of the condition for any pair of elements implies piecewise testability of $S$. In opposite case $S$ is not piecewise testable. The step has order $O(n^2)$. \end{itemize} The algorithm to verify the local threshold testability of the semigroup $S$ has order $O(n^3)$ and the algorithm to verify the piecewise testability of $S$ has order $O(n^2)$. \section{Solution of Almeida problem} We consider the following problem 5 from the monograph of Almeida $\cite {Al}$: "Is the semigroup pseudovariety defined by identities [ $x^2=0=xyxzx, xy_1...y_kxy_k...y_1=0 (k>1)$ ] decidable in polynomial time? Let us present an algorithm for checking this condition. We shall consider a binary relation $\rho$ on $n$-element semigroup $S$: $a \rho b$ for $a,b \in S$ if for some $c \in S$ holds $a=cbc$ \begin{itemize} \item Check the identities $x^2=0=xyxzx$. \item For any $b,c \in S$, suppose $b$ $\rho$ $cbc$. So we define the relation $\rho$ and let us find the transitive closure $\overline{\rho}$ of the relation $\rho$. For this aim, we consider a directed graph with nodes from $S$ where $a \to b$ iff $a \rho b$. \item for any node $a$ \begin{itemize} \item let us mark all nodes $b$ such that $a \rho b$ by the label $1$. \item for any node $x$ marked by 1, let us mark all nodes $b$ such that $x \rho b$ by label $2$. The process goes until there are edges with marked beginning and non-marked end. \end{itemize} \item now $a$ $\overline{\rho}$ $b$ if the node $b$ is labeled by some label and $a$ $\overline{\rho}^2$ $b$ if the node $b$ is labeled by the label $2$. \end{itemize} \begin{thm} For any $a,b \in S$, $a$ $\overline{\rho}^2$ $b$ iff $a=c_1...c_kbc_k...c_1$ for some $c_1$, ..., $c_k$ $(k>1)$. The considered algorithm to verify the piecewise testability of the semigroup $S$ has order $O(n^3)$ where $n$ is the size of $S$. \end{thm} Proof. According the definition, $a \rho b$ iff for some $c$ holds $b=cac$. Therefore, $a \overline{\rho} b$ iff for some $c_1,...,c_k$ we have $b=c_1...c_kac_k...c_1$ and $a \overline{\rho}^2 b$ iff for some $c_1,...,c_k$ $b=c_1...c_kac_k...c_1$ where $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 $a$ is linear in the number of edges of the graph because every edge is considered at most once. There are $n^2$ edges in the worst case. So the process of labeling nodes needs at most $n^3$ steps. \begin{thebibliography}{99} \bibitem{Al} J. Almeida, Finite Semigroups and Universal Algebra, Series in Algebra, World Sci., Vol. 3, 1995. \bibitem{BP} D. Beauquier, J.E. Pin, Factors of words, Lect. Notes in Comp. Sci, Springer, Berlin, 372(1989), 63-79. \bibitem{BS} J.A. Brzozowski, I. Simon, Characterizations of locally testable events, Discrete Math., 4, (1973), 243-271. \bibitem{K91} S. Kim, R. McNaughton, R. McCloskey, A polynomial time algorithm for the local testability problem of deterministic finite automata, IEEE Trans. Comput. 40(1991) N10, 1087-1093. \bibitem{L} G. Lallement, Semigroups and combinatorial applications, Wiley, N.Y., 1979. \bibitem{M} R. McNaughton, Algebraic decision procedure for local testability, Math.Syst.Tthery, 8( 1974), 60-76. \bibitem{MP} R. McNaughton, S. Papert, Counter-free automata, M.I.T. Press Mass., 1971. \bibitem{Si} I. Simon, Piecewise testable events, Springer, Lect. Notes in Comp. Sci., 33(1975), 214-222. \bibitem{St} J. Stern, Complexity of some problems from the theory of automata. Inf. and Control, 66(1985), 163-176. \bibitem{Tr} A.N. Trahtman, Identities of locally testable semigroups. Comm. in Algebra, v. 27, 11(1999), 5405-5412. \bibitem{Tc} A.N. Trahtman, A polynomial time algorithm for local testability and its level, Int. J. of Alg. and Comp., vol(9), No. 1 (1998), 31-39. \bibitem{Te} A.N. Trahtman, A precise estimation of the order of local testability of a deterministic finite automaton, Springer, Lect. Notes in Comp. Sci., 1436(1998), 198-212. \bibitem{TG} A.N. Trahtman, An algorithm to verify local threshold testability of deterministic finite automata. WIA99, Potsdam, Germany, July 17-20, 1999. \bibitem{T4} A.N. Trahtman, Verifying piecewise testability of finite deterministic automata. CIAA2000, London, Ontario, Canada, July 24-25, 2000. \bibitem{Z} Y. Zalcstein, Locally testable semigroups, Semigroup Forum, 5(1973), 216-227. \end{thebibliography} \end{document}