\input zb-basic
\input zb-ioport
\iteman{io-port 02147023}
\itemau{Volkov, M.V.}
\itemti{Reflexive relations, extensive transformations and piecewise testable languages of a given height.}
\itemso{Int. J. Algebra Comput. 14, No. 5-6, 817-827 (2004).}
\itemab
Let $\Sigma$ be a finite alphabet and $\Sigma^*$ be the free monoid generated by $\Sigma$. A language over $\Sigma$ is `piecewise testable of height $k$' if it belongs to the Boolean algebra generated by languages of the form $\Sigma^*x_1\Sigma^*\cdots x_m\Sigma^*$ where $0\leq m\leq k$ and $x_1,\dots,x_m\in\Sigma$. Simon gave an elegant algebraic characterization of the piecewise testable languages. Indeed, a language is piecewise testable if and only if it can be recognized by a finite $\cal J$-trivial monoid (a monoid $M$ is $\cal J$-trivial if $MaM=MbM$ implies $a=b$ for all $a,b\in M$). By ${\cal R}_n$ is denoted the monoid of all reflexive binary relations on a set with $n$ elements. It can be thought of as a submonoid of the monoid of all $n \times n$ matrices over the Boolean semiring ${\cal B}=\langle\{0,1\};+,\cdot\rangle$, that is, the submonoid consisting of matrices in which all diagonal entries are 1. By ${\cal U}_n$ is denoted the submonoid of ${\cal R}_n$ consisting of upper triangular matrices, and by ${\cal C}_n$ the monoid of all order preserving and extensive transformations of a chain with $n$ elements. The class $\bold J$ of all finite $\cal J$-trivial monoids forms a pseudovariety generated by each of the three sequences $\{{\cal U}_n\}$, $\{{\cal R}_n\}$ and $\{{\cal C}_n\}$ ($n=1,2,\dots$). For every $k=1,2,\dots$, the class of all piecewise testable languages of height $k$ corresponds to some pseudovariety of finite monoids denoted by ${\bold J}_k$. The union of the increasing sequence ${\bold J}_1\subset{\bold J}_2\subset\cdots\subset{\bold J}_k\subset\cdots$ is $\bold J$. In this paper, the author shows that for every $k$, each of ${\cal R}_{k+1}$, ${\cal U}_{k+1}$, ${\cal C}_{k+1}$ generates ${\bold J}_k$. Using this and some results of Blanchet-Sadri, the author gives a complete solution of the finite basis problem for the monoids ${\cal U}_n$, ${\cal R}_n$ and ${\cal C}_n$ for each $n$ (also called Straubing's monoids).
\itemrv{Francine Blanchet-Sadri (Greensboro)}
\itemcc{}
\itemut{piecewise testable languages; $\cal J$-trivial monoids; pseudovarieties of finite monoids; reflexive relations; order preserving transformations; extensive transformations; finite basis problem}
\itemli{doi:10.1142/S0218196704002018}
\end